配点 : 800 点
問題文
N 頂点 0 给定了一张无向边图。以下查询中 Q 请处理一个。
- add 查询(type = 1, u, v): u 和 按字典顺序比较 v 如果两点之间没有边,则添加一条边。
- complete 查询(type = 2, u, v = 0): 对所有点对 a, b 执行以下操作, u, a, b 所有点连通且 a, b 两点之间没有边时,a, b 在它们之间添加一条边。
- check 查询(type = 3, u, v): u, v 。
表示u 和
按字典顺序比较 v 如果存在直接连接的边
Yes,否则 在第No。 我锻炼
制約
- 2 \leq N \leq 100,000
- 1 \leq Q \leq 200,000
- type_i = 1, 2, 3
- 1 \leq u_i \leq N
- 在 add、check 查询中 1 \leq v_i \leq N 和 u_i \neq v_i
- 在 complete 查询中 v_i = 0
- 所有输入值均为整数
入力
输入是按以下格式从标准输入给出的。
N Q type_1 u_1 v_1 type_2 u_2 v_2 : type_Q u_Q v_Q
出力
对于每个check查询,Yes或No请输出。
入力例 1
3 6 1 1 2 1 2 3 3 1 2 3 1 3 2 1 0 3 1 3
出力例 1
Yes No Yes
1, 2 在第 n 个查询中(1, 2), (2, 3)会添加边。 然后,5 在第 n 个查询中(1, 3) 在两点之间会添加边。
入力例 2
3 6 2 3 0 3 1 3 1 3 1 2 3 0 1 1 2 3 2 1
出力例 2
No Yes
入力例 3
8 20 1 3 6 2 6 0 2 2 0 2 7 0 1 7 3 3 2 6 1 4 2 3 3 7 1 2 6 2 4 0 2 2 0 3 3 1 2 8 0 2 8 0 1 8 2 2 7 0 3 5 4 1 4 2 3 5 7 3 2 3
出力例 3
No Yes No No No Yes