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での動作

入力される各決勝進出者の組は、次のようになる。

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

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

まず、中心を 1 とする。
相方候補として、1 以外の全員を st に入れる。

st: {2, 3, 4, 5}

組 (1, 2) には中心 1 が含まれているので、st は変更しない。

組 (3, 4) には中心 1 が含まれていない。
相方は 3 または 4 でなければならないので、st を集合 {3, 4} との共通部分に絞る。

st: {3, 4}

組 (1, 3) には中心 1 が含まれているので、st は変更しない。

組 (2, 3) には中心 1 が含まれていない。
st を集合 {2, 3} との共通部分に絞る。

st: {3}

組 (2, 5) にも中心 1 が含まれていない。
しかし、現在の候補 3 はこの組に含まれないので、st は空になる。

st: {}

したがって、中心が 1 の組は result に追加されない。

次に、中心を 2 とする。
相方候補として、2 以外の全員を st に入れる。

st: {1, 3, 4, 5}

組 (1, 2) には中心 2 が含まれているので、st は変更しない。

組 (3, 4) には中心 2 が含まれていないので、st を集合 {3, 4} との共通部分に絞る。

st: {3, 4}

組 (1, 3) にも中心 2 が含まれていないので、st を集合 {1, 3} との共通部分に絞る。

st: {3}

残りの組 (2, 3) と (2, 5) には中心 2 が含まれているので、st は変更しない。

最後まで残った 3 は、中心 2 の相方にできる。
組 (2, 3) を result に追加する。

result: {(2, 3)}

最後に、result の要素数である $1$ を出力する。

注意点

特になし。

別解

特になし。