D - Propagating Edges

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 800

問題文

N 頂点 0 辺の無向グラフが与えられます。以下のクエリを Q 個処理して下さい。

  • addクエリ(type = 1, u, v): uv の間に辺が無ければ辺を貼る。
  • completeクエリ(type = 2, u, v = 0): 全ての頂点対 a, b について以下を行う, u, a, b がすべて連結で,かつ a, b 間に辺がない場合,a, b の間に辺を貼る。
  • checkクエリ(type = 3, u, v): u, v が与えられる。uv を直接結ぶ辺がある場合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クエリに対し、YesNoを出力してください。


入力例 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 つ目のクエリで(1, 2), (2, 3)に辺が張られます。 そして、5 つ目のクエリで(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