Score : $500$ points

问题描述

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

总共需要处理 $Q$ 个操作。

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

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

1 $X$ $Y$

类型 $2$: 将当前盒子中球总数为 $k$ 时的下一个球（即球 $k+1$）放入盒子 $X$。

2 $X$

类型 $3$: 报告包含球 $X$ 的盒子的编号。

3 $X$

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:45:06