K - Checking Connectivity Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 6 点

問題文

N 頂点 M 辺の無向グラフがあります。初め、 i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

Q 個のクエリを処理してください。 i 番目のクエリは t_i,x_i,y_i を用いて以下のように表されます。

  • t_i=1 の時、頂点 x_i と頂点 y_i を結ぶ辺を追加してください。なお、一つのテストケースに含まれるこの種類のクエリは 10 個以下です。
  • t_i=2 の時、頂点 x_i と頂点 y_i を結ぶ辺を削除してください。
  • t_i=3 の時、頂点 x_i と頂点 y_i が同じ連結成分に属するならば Yes と、そうでなければ No と出力してください。

制約

  • 1 \leq N,M,Q \leq 10^5
  • 1 \leq a_i \lt b_i \leq N
  • i \neq j ならば (a_i,b_i) \neq (a_j,b_j)
  • t_i \in \{ 1,2,3 \}
  • 1 \leq x_i \lt y_i \leq N
  • t_i=1 を満たす i は 10 個以下
  • t_i=1 ならば、そのクエリの時点で頂点 x_i と頂点 y_i を結ぶ辺が存在しない
  • t_i=2 ならば、そのクエリの時点で頂点 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 を満たすクエリが存在しない場合もあります。






Score : 6 points







Problem Statement
There is an undirected graph with N vertices and M edges. Initially, the i-th edge connects Vertex a_i and Vertex b_i.


Process Q queries. The i-th query is represented by t_i, x_i, and y_i as follows.


    

  • If t_i=1, add an edge connecting Vertex x_i and Vertex y_i. There are at most 10 queries of this kind in a single test case.
    • 

  • If t_i=2, delete the edge connecting Vertex x_i and Vertex y_i.
    • 

  • If t_i=3, print Yes if Vertex x_i and Vertex y_i belong to the same connected component, and No otherwise.
    • 












Constraints
    

  • 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
    • 

  • There are at most 10 indices i such that t_i=1.
    • 

  • If t_i=1, there is no edge connecting Vertex x_i and Vertex y_i when the query is given.
    • 

  • If t_i=2, there is an edge connecting Vertex x_i and Vertex y_i when the query is given.
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


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












Output
For each query such that t_i=3, print the answer and then a newline.















Sample Input 1
5 3
1 3
2 3
4 5
4
1 1 4
3 1 5
2 2 3
3 1 5












Sample Output 1
Yes
Yes














Sample Input 2
5 2
1 3
2 4
2
2 2 4
2 1 3












Sample Output 2


There may be no query such that t_i=3.