← 返回题目列表

AtCoder · abc225_d

G. 玩火车

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

分数: 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 查询已处理。