← 返回题目列表

AtCoder · past202209_k

K. 检查连接性

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

分数: 6 点

问题陈述

有一个无向图 N 顶点和 M 边缘。最初, i第一条边连接顶点 a_i 和顶点 b_i.

流程 Q 查询。的 i第一个查询表示为 t_i, x_i,和 y_i 如下。

  • If t_i=1,添加一条连接 Vertex 的边 x_i 和顶点 y_i。最多有 10 在单个测试用例中进行此类查询。
  • If t_i=2,删除连接Vertex的边 x_i 和顶点 y_i.
  • If t_i=3,打印 Yes 如果顶点 x_i 和顶点 y_i 属于同一连通分量,并且 No 否则。

约束

  • 1 \leq N,M,Q \leq 10^5
  • 1 \leq a_i \lt b_i \leq N
  • (a_i,b_i) \neq (a_j,b_j) if i \neq j.
  • t_i \in \{ 1,2,3 \}
  • 1 \leq x_i \lt y_i \leq N
  • 最多有 10 指数 i 这样 t_i=1.
  • If t_i=1,没有边连接 Vertex x_i 和顶点 y_i 给出查询时。
  • If t_i=2,有一条边连接 Vertex x_i 和顶点 y_i 给出查询时。
  • 输入中的所有值都是整数。

输入

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

N M
a_1 b_1
\vdots
a_M b_M
Q
t_1 x_1 y_1
\vdots
t_Q x_Q y_Q

输出

对于每个查询,使得 t_i=3,打印答案,然后打印换行符。


样本输入 1

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

示例输出 1

Yes
Yes

示例输入 2

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

示例输出 2


可能没有这样的查询 t_i=3.