F - BOX Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 つ、整数として出力せよ。

入力例 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

出力例 1

5
4
3
1
3

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

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

Score : 500 points

Problem Statement

There are N boxes numbered 1,2,\ldots,N, and 10^{100} balls numbered 1,2,\dots,10^{100}. Initially, box i contains just ball i.

Process a total of Q operations that will be performed.

There are three types of operations: 1, 2, and 3.

Type 1: Put all contents of box Y into box X. It is guaranteed that X \neq Y.

1 X Y

Type 2: Put ball k+1 into box X, where k is the current total number of balls contained in the boxes.

2 X

Type 3: Report the number of the box that contains ball X.

3 X

Constraints

  • All values in the input are integers.
  • 2 \le N \le 3 \times 10^5
  • 1 \le Q \le 3 \times 10^5
  • For each type-1 operation, 1 \le X,Y \le N and X \neq Y.
  • For each type-2 operation, 1 \le X \le N.
  • For each type-3 operation, ball X is contained in some box at that point.
  • There is at least one type-3 operation.

Input

The input is given from Standard Input in the following format.
Here, op_i represents the i-th operation.

N Q
op_1
op_2
\vdots
op_Q

Output

For each type-3 operation, print a line containing the response as an integer.

Sample Input 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

Sample Output 1

5
4
3
1
3

This input contains ten operations.

  • The first operation is of type 3. Ball 5 is in box 5.
  • The second operation is of type 1. Put all contents of box 4 into box 1.
    • Box 1 now contains balls 1 and 4, and box 4 is now empty.
  • The third operation is of type 2. Put ball 6 into box 1.
  • The fourth operation is of type 2. Put ball 7 into box 4.
  • The fifth operation is of type 3. Ball 7 is in box 4.
  • The sixth operation is of type 1. Put all contents of box 1 into box 3.
    • Box 3 now contains balls 1, 3, 4, and 6, and box 1 is now empty.
  • The seventh operation is of type 3. Ball 4 is in box 3.
  • The eighth operation is of type 1. Put all contents of box 4 into box 1.
    • Box 1 now contains ball 7, and box 4 is now empty.
  • The ninth operation is of type 3. Ball 7 is in box 1.
  • The tenth operation is of type 3. Ball 6 is in box 3.