F - 箱子

得分: 500 分

问题描述

有 $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+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
...
op_Q

输出

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

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

这个样例包含了十次操作。

• 第一次操作是类型 $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$ 中。