分数: 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 \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.