分数: 400 点
问题陈述
高桥正在玩玩具火车,连接和断开它们。
有 N 玩具火车车厢,车号:汽车 1, 汽车 2, \ldots, 汽车 N.
最初,所有汽车都是分开的。
你将得到 Q 查询。按照给定的顺序处理它们。 查询分为以下三种。
-
1 x y: 连接汽车前部 y 到汽车后部 x.
保证:- x \neq y
- 在此查询之前,没有列车连接到 Car 的后部 x;
- 在此查询之前,没有火车连接到 Car 的前面 y;
- 在此查询之前,汽车 x 和汽车 y 属于不同的连通分量。
-
2 x y: 断开汽车前部的连接 y 从汽车后部 x.
保证:- x \neq y;
- 在此查询之前,Car 的前面 y 直接连接到汽车后部 x.
-
3 x:打印属于包含 Car 的连接组件的汽车编号 x, 从前往后.
约束
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq x \leq N
- 1 \leq y \leq N
- 输入中的所有值都是整数。
- 所有查询都满足问题陈述中的条件。
- 格式的查询
3 x最多要求打印 10^6 车辆总数。
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
的 i第一个查询 \mathrm{query}_i 以整数开头 c_i (1, 2,或 3) 代表查询的类型,后跟 x 和 y if c_i = 1 or 2,然后是 x if c_i = 3.
简而言之,每个查询都采用以下三种格式之一:
1 x y
2 x y
3 x
输出
如果查询 c_i = 3 要求打印值 j_1, j_2, \ldots, j_M,输出以下行:
M j_1 j_2 \ldots j_M
您的输出应包括 q 行,其中 q 是查询的数量 c_i = 3.
的 k第行 (1 \leq k \leq q) 应包含对 k-第一个这样的查询。
示例输入 1
7 14 1 6 3 1 4 1 1 5 2 1 2 7 1 3 5 3 2 3 4 3 6 2 3 5 2 4 1 1 1 5 3 2 3 4 3 6
示例输出 1
5 6 3 5 2 7 2 4 1 5 6 3 5 2 7 4 1 5 2 7 1 4 2 6 3
下图显示了第一次时的车辆 5 查询已处理。
例如,汽车 2 与 Cars 属于相同的连接组件 3, 5, 6, 7,与包含 Cars 的连接组件不同 1, 4.

下图显示了第一次时的车辆 11 查询已处理。
