ABC469 D - The Big Two

考え方

まず、条件を満たす可能性がある組は $N(N-1)/2$ 通りありそうに見える。
しかし、実は最初の $1$ 試合に出ているどちらかが含まれていなければ条件を満たさない。
その $1$ つだけで、候補は $2N-3$ 通りにまで減る。
よって、この中で答えの組を探して全て列挙するのも、高速にやれば十分間に合う。

まず、最初の $1$ 試合の $1$ 人目に注目して考えて、条件を満たす組を列挙する。
もう $1$ 人として可能性がある人を set で管理する。
最初は、注目している人以外すべてを入れておく。
$1$ 試合ずつ見て、注目している人がいない試合だったら、set からその $2$ 人以外削除する。
（実装上は、その $2$ 人が set にいるか確認をして、作り直して swap すると高速）
最後に残った人が、最初の $1$ 試合の $1$ 人目とペアになれる人である。

同様に最初の $1$ 試合の $2$ 人目にも注目して考える。

あとは、最初の $2$ 人の組を重複カウントしないように気を付けて全組数を数えればよい。

計算量は $O((M+N)\log N)$ である。

入力例1での動作

入力を受け取る。

n: 5
m: 5
a, b:
(1, 2)
(3, 4)
(1, 3)
(2, 3)
(2, 5)

条件を満たす組には、最初の決勝進出者である $1$ または $2$ の少なくとも一方が含まれる。
そこで、この $2$ 人を順に中心として調べる。

まず、中心を $1$ とする。
最初の相方候補は $1$ 以外の全員なので、$\{2,3,4,5\}$ である。

中心 $1$ が含まれない決勝だけを見ると、候補は次のように絞られる。

したがって、中心が $1$ の組は存在しない。

次に、中心を $2$ とする。
最初の相方候補は $\{1,3,4,5\}$ である。

中心 $2$ が含まれない決勝だけを見ると、候補は次のように絞られる。

最後まで $3$ が残るので、条件を満たす組は $(2,3)$ の $1$ 組である。
したがって、答えは $1$ となる。

注意点

特になし。

別解

特になし。