AT_abc279_f [ABC279F] BOX

有 $N$ 个箱子 $1,2,\dots,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$

输入按以下格式从标准输入读入。 其中 $op_i$ 表示第 $i$ 次操作。 > $N$ $Q$ > $op_1$ > $op_2$ > $\vdots$ > $op_Q$

对于每个类型 $3$ 的操作，输出答案，每行一个整数。

### 约束条件 - 输入均为整数。 - $2 \leq N \leq 3 \times 10^5$ - $1 \leq Q \leq 3 \times 10^5$ - 对于类型 $1$ 的操作，$1 \leq X,Y \leq N$ 且 $X \neq Y$ - 对于类型 $2$ 的操作，$1 \leq X \leq N$ - 对于类型 $3$ 的操作，保证此时编号为 $X$ 的球一定在某个箱子中 - 至少有一次类型 $3$ 的操作 ### 样例解释 1 本输入包含 $10$ 次操作。 - 第 $1$ 次操作为类型 $3$。球 $5$ 在箱子 $5$ 中。 - 第 $2$ 次操作为类型 $1$。将箱子 $4$ 的所有球放入箱子 $1$。 - 此时箱子 $1$ 中有球 $1,4$，箱子 $4$ 为空。 - 第 $3$ 次操作为类型 $2$。将球 $6$ 放入箱子 $1$。 - 第 $4$ 次操作为类型 $2$。将球 $7$ 放入箱子 $4$。 - 第 $5$ 次操作为类型 $3$。球 $7$ 在箱子 $4$ 中。 - 第 $6$ 次操作为类型 $1$。将箱子 $1$ 的所有球放入箱子 $3$。 - 此时箱子 $3$ 中有球 $1,3,4,6$，箱子 $1$ 为空。 - 第 $7$ 次操作为类型 $3$。球 $4$ 在箱子 $3$ 中。 - 第 $8$ 次操作为类型 $1$。将箱子 $4$ 的所有球放入箱子 $1$。 - 此时箱子 $1$ 中有球 $7$，箱子 $4$ 为空。 - 第 $9$ 次操作为类型 $3$。球 $7$ 在箱子 $1$ 中。 - 第 $10$ 次操作为类型 $3$。球 $6$ 在箱子 $3$ 中。 由 ChatGPT 4.1 翻译