← 返回题目列表

AtCoder · soundhound2018_summer_final_d

D. 传播边缘

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

配点 : 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