配点 : $400$ 点

問題文

高橋君は電車のおもちゃを連結させたり分離させたりして遊んでいます。 電車は $N$ 個あり、電車 $1$ 、電車 $2$ 、$\ldots$ 、電車 $N$ と名前がついています。 はじめ電車どうしは連結しておらず全てバラバラです。

クエリが $Q$ 個与えられるので、与えられた順番に処理してください。 クエリは次の $3$ 種類のいずれかです。

• 1 x y ：電車 $x$ の後部と、電車 $y$ の前部を連結させる。 以下のことが保証されます。
  • $x \neq y$
  • クエリを処理する直前に、電車 $x$ の後部と連結している電車は存在しない
  • クエリを処理する直前に、電車 $y$ の前部と連結している電車は存在しない
  • クエリを処理する直前に、電車 $x$ と電車 $y$ は異なる連結成分に属する
• 2 x y ：電車 $x$ の後部と、電車 $y$ の前部を分離させる。 以下のことが保証されます。
  • $x \neq y$
  • クエリを処理する直前に、電車 $x$ の後部と電車 $y$ の前部は直接連結している
• 3 x ：電車 $x$ が含まれる連結成分に属する電車の番号を、先頭から順番に全て出力する。

制約

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq x \leq N$
• $1 \leq y \leq N$
• 入力は全て整数
• クエリは全て問題文の条件を満たす
• 3 x の形式のクエリで出力する電車の番号の個数の合計は $10^6$ 以下

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$\mathrm{query}_1$

$\mathrm{query}_2$

$\vdots$

$\mathrm{query}_Q$

$i$ 番目のクエリ $\mathrm{query}_i$ では、まずクエリの種類 $c_i$（ $1, 2, 3$ のいずれか）が与えられる。 $c_i = 1,2$ の場合は $x,y$ が追加で与えられ、$c_i =3$ の場合は $x$ が追加で与えられる。

すなわち、各クエリは以下に示す $3$ つの形式のいずれかである。

$1$ $x$ $y$

$2$ $x$ $y$

$3$ $x$

出力

ある $c_i = 3$ のタイプのクエリにおいて、出力すべき値が $j_1, j_2, \ldots , j_M$ であるとする。 このとき以下の形式で $1$ 行に出力せよ。

$M$ $j_1$ $j_2$ $\ldots$ $j_M$

$c_i = 3$ のタイプのクエリの数を $q$ として、$q$ 行出力せよ。 $k (1 \leq k \leq q)$ 行目では $k$ 番目のそのようなクエリに対する答えを出力せよ。

7 14
1 6 3
1 4 1
1 5 2
1 2 7
1 3 5
3 2
3 4
3 6
2 3 5
2 4 1
1 1 5
3 2
3 4
3 6

5 6 3 5 2 7
2 4 1
5 6 3 5 2 7
4 1 5 2 7
1 4
2 6 3

$\mathrm{query}_5$ まで処理した時、電車は以下のようになっています。 この時、たとえば電車 $2$ は、電車 $3,5,6,7$ と同じ連結成分に属していますが、電車 $1,4$ とは同じ連結成分に属していません。

$\mathrm{query}_{11}$ まで処理した時、電車は以下のようになっています。