#16 Dynamic connectivity

製作者:QCFium

難易度
7

解説


## 問題 $N$頂点のグラフがあります。最初グラフに辺はありません。 ここに$Q$回のクエリが飛んでくるので処理してください。 $i$回目のクエリでは$T_i, X_i, Y_i$が与えられます。 - $T_i=1$のとき : グラフの頂点$X_i$と頂点$Y_i$の間に新たな無向辺を追加する - 追加後もグラフは単純であることが保証される - $T_i=2$のとき : グラフの頂点$X_i$と頂点$Y_i$の間の辺を削除する - そのような辺が存在することが保証される - $T_i=3$のとき : グラフ上で頂点$X_i$と頂点$Y_i$の間にパスが存在するかを判定する ## 入力 $N \hspace{7pt} Q$ $T_1 \hspace{7pt} X_1 \hspace{7pt} Y_1$ $T_2 \hspace{7pt} X_2 \hspace{7pt} Y_2$ $T_3 \hspace{7pt} X_3 \hspace{7pt} Y_3$ $\hspace{21pt} \vdots$ $T_Q \hspace{7pt} X_Q \hspace{7pt} Y_Q$ ## 制約 $2 \le N \le 10^5$ $1 \le Q \le 10^5$ $1 \le T_i \le 3(1 \le i \le Q)$ $1 \le X_i \lt Y_i \le N(1 \le i \le Q)$ 入力は全て整数 ## 小課題 この問題はいくつかの小課題に分割される。 ### 小課題1 [満点の30%] $1 \le N \le 1000$ $1 \le Q \le 1000$ ### 小課題2 [満点の30%] $T_i $は$2$でない$(1 \le i \le Q)$ ### 小課題3 [満点の40%] 追加の制約はない ## 出力 $T_i=3$な各クエリについて、パスが存在するなら```Yes```を、存在しないなら```No```を一行ずつ出力してください。 ## 例 ### 入力例1 ``` 3 5 1 1 2 3 1 2 3 3 2 1 2 3 3 1 3 ``` ### 出力例1 ``` Yes No Yes ``` この例は小課題1,2の追加制約を満たします。 ### 入力例2 ``` 3 7 1 1 2 1 2 3 3 1 3 2 1 2 3 1 2 1 1 3 3 1 2 ``` ### 出力例2 ``` Yes No Yes ``` この例は小課題1の追加制約を満たします。
提出