東京大学プログラミングコンテスト2012

C - 森ですか?


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

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


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

各クエリは (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行に出力せよ.

制約

部分点

この問題の判定には,50点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は以下の条件を満たす.


入力例 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

Submit提出する