102795: [AtCoder]ABC279 F - BOX

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$.

问题描述

有编号为$1,2,\ldots,N$的$N$个盒子，以及编号为$1,2,\dots,10^{100}$的$10^{100}$个球。最初，第$i$个盒子中只包含球$i$。

处理总共要执行的$Q$个操作。

操作有三种类型：$1$、$2$和$3$。

类型$1$：将盒子$Y$中的所有内容放入盒子$X$。保证$X \neq Y$。

1 $X$ $Y$

类型$2$：将球$k+1$放入盒子$X$，其中$k$是当前盒子中包含的球的总数量。

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$的操作。

输入

输入从标准输入以以下格式给出。 此处，$op_i$表示第$i$个操作。

$N$ $Q$
$op_1$
$op_2$
$\vdots$
$op_Q$

输出

对于每个类型$3$的操作，打印一行包含响应的整数。

样例输入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

此输入包含十个操作。

• 第一个操作是类型$3$。球$5$在盒子$5$中。
• 第二个操作是类型$1$。将盒子$4$中的所有内容放入盒子$1$。
  • 现在，盒子$1$包含球$1$和$4$，盒子$4$为空。
• 第三个操作是类型$2$。将球$6$放入盒子$1$。
• 第四个操作是类型$2$。将球$7$放入盒子$4$。
• 第五个操作是类型$3$。球$7$在盒子$4$中。
• 第六个操作是类型$1$。将盒子$1$中的所有内容放入盒子$3$。
  • 现在，盒子$3$包含球$1$、$3$、$4$和$6$，盒子$1$为空。
• 第七个操作是类型$3$。球$4$在盒子$3$中。
• 第八个操作是类型$1$。将盒子$4$中的所有内容放入盒子$1$。
  • 现在，盒子$1$包含球$7$，盒子$4$为空。
• 第九个操作是类型$3$。球$7$在盒子$1$中。
• 第十个操作是类型$3$。球$6$在盒子$3$中。