G - Breaking Friends

通常と異なる実行時間制限に注意してください。

問題

$N$ 人の PCP 部員がいて、それぞれに $1$ から $N$ までの番号がついています。
$1 \leq i \leq M$ を満たす $i$ について、部員 $A_i$ と部員 $B_i$ は友達です。

また、「知り合い」という関係も存在しています。「友達」や「知り合いの友達」は、全員知り合いで、そうでない人は知り合いではありません。

部員たちは 1 人以上で「グループ」をつくっています。全員が何らかのグループに所属しています。
グループのメンバーは、全員がほかのメンバーと互いに知り合いの関係にあり、また各部員は所属していないグループのメンバーは知りません。

$Q$ 回の「できごと」（ $event$ ）が発生するので、適切に対処してください。各「できごと」の内容は、次のうちのどれか一つです。

1. 友達だった部員 $S_q$ と $T_q$ が絶交する。互いに友達ではなかったことになり、相手を介して知っていた「知り合い」は知らなかったことになる。これに伴って、グループは再構成される。（分裂することがある）
2. 部員 $S_q$ と $T_q$ が知り合いなら 「 Yes 」 , 知り合いでないなら 「 No 」 を出力する。
3. 部員 $X_q$ の所属するグループのメンバーを全員出力する。このとき、部員の番号の小さい順に出力する必要がある。
4. 部員 $X_q$ の所属するグループの人数を出力する。

BONUS!

上記だけでは 120 点ですが、つぎの「できごと」も処理した場合、満点（150点）が得られます。

5. 部員 $S_q$ と $T_q$ が友達になる。知り合いも増える。これに伴って、グループは再編成される。なお、この二人は新たな友達ではなく絶交していたものが仲直りしているという可能性もある。

制約

• $2\leq N\leq 200000$
• $1 \leq M \leq min(200000, {}_N \mathrm{C}_2 )$
• $1 \leq A_i < B_i \leq N$ $(1 \leq i \leq M)$
• $(A_i, B_i) \neq (A_j, B_j)$ $(i \neq j)$
• $1 \leq Q \leq 200000$
• できごと 1 と 2 と 5 について、
  • $1 \leq S_q < T_q \leq N$ $(1 \leq q \leq Q)$
• できごと 3 と 4 について、
  • $1 \leq X_q \leq N$ $(1 \leq q \leq Q)$
• できごと 1 について、
  • 発生前、 $S_q$ と $T_q$ は友達関係にある
• できごと 3 について、
  • 発生回数は 80 回以下
• できごと 5 について、
  • 発生回数は 3 回以下
  • 発生前、 $S_q$ と $T_q$ は友達関係にはない
• 入力はすべて整数

小課題

1. (30点) $N \leq 6$ 、 $1 \leq Q \leq 100$ 、できごと 3 、 4 、 5 は起こらない
2. (20点) $N, M \leq 300$ 、 $1 \leq Q \leq 100$ 、できごと 4 、 5 は起こらない
3. (70点) できごと 5 は起こらない
4. (30点) できごと 5 が起こる

入力

$N~M$

$A_1~B_1$

$A_2~B_2$

$\vdots$

$A_M~B_M$

$Q$

$event_1$

$event_2$

$\vdots$

$event_Q~$

各 $event_q$ $(1 \leq q \leq Q)$ は、次のように与えられる。

1. $1 \; S_q \; T_q$
2. $2 \; S_q \; T_q$
3. $3 \; X_q$
4. $4 \; X_q$
5. $5 \; S_q \; T_q$

出力

できごと 2 3 4 の結果を改行区切りで出力してください。

• 2: Yes または No を結果に応じて出力
• 3: $X_q$ と同じグループに所属する部員の番号を昇順に空白区切りで出力
• 4: $X_q$ と同じグループに所属する部員の人数を出力

$N~M$

$A_1~B_1$

$A_2~B_2$

$\vdots$

$A_M~B_M$

$Q$

$event_1$

$event_2$

$\vdots$

$event_Q~$

入出力例

入力例 1

4 4 
1 2
1 3
1 4
2 4
5
3 1
1 1 2
2 1 2
1 1 4
3 1
Copy

出力例 1

1 2 3 4 
Yes
1 3 
Copy

入力例 2

8 4
1 2
2 3
2 4
7 8
15
2 1 4
3 3
1 7 8
4 7
5 2 5
3 3
1 2 4
3 3
1 2 3
3 1
5 2 3
5 3 5
3 4
1 2 3
3 1
Copy

出力例 2

Yes
1 2 3 4 
1 
1 2 3 4 5 
1 2 3 5 
1 2 5 
4 
1 2 3 5 
Copy