配点 : $500$ 点

問題文

$N$ 個の箱 $1,2,\dots,N$ と、 $10^{100}$ 個のボール $1,2,\dots,10^{100}$ があります。 最初、箱 $i$ にはボール $i$ のみが入っています。

ここに以下の操作が合計 $Q$ 回行われるので、処理してください。

操作にはタイプ $1,2,3$ の $3$ 種類があります。

タイプ $1$ : 箱 $X$ に箱 $Y$ の中身を全て入れる。 この操作では $X \neq Y$ が保証される。

1 X Y

タイプ $2$ : 現在いずれかの箱に入っているボールの数の合計を $k$ とすると、箱 $X$ にボール $k+1$ を入れる。

2 X

タイプ $3$ : ボール $X$ が入っている箱の番号を答える。

3 X

制約

• 入力は全て整数
• $2 \le N \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• タイプ $1$ の操作について、 $1 \le X,Y \le N$ かつ $X \neq Y$
• タイプ $2$ の操作について、 $1 \le X \le N$
• タイプ $3$ の操作について、その時点でボール $X$ がいずれかの箱に入っている
• タイプ $3$ の操作が少なくとも $1$ つ与えられる

入力

入力は以下の形式で標準入力から与えられる。 但し、 $op_i$ は $i$ 回目の操作を表す。

$N$ $Q$

$op_1$

$op_2$

$\vdots$

$op_Q$

出力

各タイプ $3$ の操作に対して、答えを $1$ 行に $1$ つ、整数として出力せよ。

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

5
4
3
1
3

この入力は $10$ 個の操作を含みます。

• $1$ 回目の操作はタイプ $3$ です。ボール $5$ は箱 $5$ に入っています。
• $2$ 回目の操作はタイプ $1$ です。箱 $1$ に箱 $4$ の中身を全て入れます。- 箱 $1$ の中身はボール $1,4$ 、箱 $4$ の中身は空になります。
• 箱 $1$ の中身はボール $1,4$ 、箱 $4$ の中身は空になります。
• $3$ 回目の操作はタイプ $2$ です。箱 $1$ にボール $6$ を入れます。
• $4$ 回目の操作はタイプ $2$ です。箱 $4$ にボール $7$ を入れます。
• $5$ 回目の操作はタイプ $3$ です。ボール $7$ は箱 $4$ に入っています。
• $6$ 回目の操作はタイプ $1$ です。箱 $3$ に箱 $1$ の中身を全て入れます。- 箱 $3$ の中身はボール $1,3,4,6$ 、箱 $1$ の中身は空になります。
• 箱 $3$ の中身はボール $1,3,4,6$ 、箱 $1$ の中身は空になります。
• $7$ 回目の操作はタイプ $3$ です。ボール $4$ は箱 $3$ に入っています。
• $8$ 回目の操作はタイプ $1$ です。箱 $1$ に箱 $4$ の中身を全て入れます。- 箱 $1$ の中身はボール $7$ 、箱 $4$ の中身は空になります。
• 箱 $1$ の中身はボール $7$ 、箱 $4$ の中身は空になります。
• $9$ 回目の操作はタイプ $3$ です。ボール $7$ は箱 $1$ に入っています。
• $10$ 回目の操作はタイプ $3$ です。ボール $6$ は箱 $3$ に入っています。