C - 森ですか?
Editorial
/

頂点数5の完全グラフの例

左のグラフのときに(1, 3)というクエリが来ると,頂点1と3の間の辺を取り除く.

左のグラフのときに(1, 3)というクエリが来ると,頂点1と3の間に辺を加える.

森でないグラフの例

森の例

全体がつながっていなくても森になる.


Time Limit: 2 sec / Memory Limit: 256 MB
問題
N 頂点の完全グラフと M 個のクエリが与えられる. グラフとは,頂点と呼ばれる点と,辺と呼ばれる頂点と頂点を結ぶ線からなる図形の事である. 完全グラフは,すべての2つの頂点に対してそれを結ぶ辺が1つ存在するようなグラフの事である.

頂点数5の完全グラフの例
各クエリは (S, T) という形で与えられ,
- 頂点 S と T の間に辺があるなら取り除く
- 頂点 S と T の間に辺がないなら付け加える
という操作を行う.

左のグラフのときに(1, 3)というクエリが来ると,頂点1と3の間の辺を取り除く.

左のグラフのときに(1, 3)というクエリが来ると,頂点1と3の間に辺を加える.
各クエリ後に,グラフが森かどうかを出力するプログラムを作成せよ. 森とは,閉路(下図の1→4→5→1のようにループになっているところ)を持たないグラフの事である.

森でないグラフの例

森の例

全体がつながっていなくても森になる.
入力
N M S_1 T_1 ... S_m T_m
入力の1行目には完全グラフの頂点数 N と, クエリの個数 M が与えられる. 続く M 行にクエリの情報(S_i, T_i)が与えられる.
ただし、グラフの頂点は 1 から N まで番号付けされているとする.
出力
各クエリ毎に処理した結果が森ならば yes
, そうでないならば no
と1行に出力せよ.
制約
- 2 \leq N \leq 100,000
- 0 \leq M \leq 100,000
- 1 \leq S_i, T_i \leq N
- S_i \neq T_i
部分点
この問題の判定には,50点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は以下の条件を満たす.
- 2 \leq N \leq 100
- 0 \leq M \leq 100
入力例 1
3 4 1 2 1 2 2 3 1 2
入力例 1 に対する出力例
yes no yes yes
クエリに対して,下図のようにグラフが変化する.

入力例 2
4 4 1 2 1 4 2 3 3 4
入力例 2 に対する出力例
no no yes yes