← 返回题目列表

AtCoder · abc279_f

I. 盒子

中文机器翻译题面 查看原题

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