← 返回题目列表

AtCoder · utpc2012_03

C. 这是森林吗?

中文机器翻译题面 查看原题

問題

N 顶点的完全图和 M 给定的查询个数。 图是由称为顶点的点和连接顶点的线称为边构成的图形。 完全图是指对于所有任意两个顶点之间都存在唯一的一条边相连的图。


顶点数为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

输入的第一行为完全图的顶点数 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