← 返回题目列表

AtCoder · past202112_g

G. 连接性

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

分数: 6 点

问题陈述

有一个无向图 N 顶点。最初,没有两个顶点通过边连接。
处理 Q 按给出的顺序查询。
下面显示了两种查询。

  • 1 u v:如果没有直接连接Vertex的边 u 和顶点 v,添加一条无向边连接它们;如果存在这样的边,则将其删除。

  • 1 u v: 是否可以从 Vertex 获取 u 到顶点 最终图表中的 v 通过遍历边缘,打印 Yes;否则,打印 No.

约束

  • 2 \leq N \leq 100
  • 1 \leq Q \leq 10000
  • 1 \leq u,v \leq N
  • u \neq v
  • 至少有一个第二类查询。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N Q
query_1
query_2
\vdots
query_Q

每个 query_i 在 2-nd 通过 (Q+1)第行采用以下格式之一:

1 u v
2 u v

输出

按照给出的顺序打印对第二类查询的响应,并用换行符分隔。


示例输入 1

3 5
1 1 2
1 3 2
2 1 3
1 2 1
2 1 3

示例输出 1

Yes
No
  • 就在之前 1-st 查询,顶点 1 和顶点 2 没有通过边连接,因此我们添加一条边。
  • 就在之前 2-nd 查询,顶点 3 和顶点 2 没有通过边连接,因此我们添加一条边。
  • 当时 3-rd查询,我们可以遍历添加的边 1-st 和 2-nd 查询转到 Vertex 1 \to 顶点 2 \to 顶点 3,所以我们打印 Yes.
  • 就在之前 4第一个查询,顶点 3 和顶点 2 由边直接连接,因此我们将其删除。
  • 当时 5第次查询,仅连接Vertex的边 1 和顶点 2 存在,这不允许我们从 Vertex 获取 1 到顶点 最终图表中的 3,所以我们打印 No.