Play Train

题目描述

Takahashi 在玩玩具火车，连接和断开它们。
有 $N$ 节玩具火车车厢，编号为：Car $1$、Car $2$、$\ldots$、Car $N$。
最初，所有车厢都是分开的。 将给出 $Q$ 个查询。按给定顺序处理它们。 有三种类型的查询，如下。

$1 x y$: 将 Car $y$ 的前端连接到 Car $x$ 的后端。
保证：

$x \neq y$ 在此查询之前，Car $x$ 的后端没有连接任何列车； 在此查询之前，Car $y$ 的前端没有连接任何列车； 在此查询之前，Car $x$ 和 Car $y$ 属于不同的连通分量。

$2 x y$: 将 Car $y$ 的前端从 Car $x$ 的后端断开。
保证：

$x \neq y$； 在此查询之前，Car $y$ 的前端直接连接到 Car $x$ 的后端。

$3 x$: 从前到后打印属于包含 Car $x$ 的连通分量的车厢编号，从前到后。

输入格式

输入按下述格式从标准输入给出： $N$ $Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$

第 $i$ 个查询 $\mathrm{query}_i$ 以一个整数 $c_i$（$1$、$2$ 或 $3$）开头，表示查询的类型；若 $c_i = 1$ 或 $2$ 则后面跟随 $x$ 和 $y$，若 $c_i = 3$ 则后面跟随 $x$。 简言之，每个查询为以下三种格式之一： $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$ 个此类查询的回答。

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

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

提示

$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$ 个车厢编号。下图展示了处理前 $5$ 个查询后车厢的情况。
例如，Car $2$ 与 Cars $3, 5, 6, 7$ 属于同一连通分量，该连通分量不同于包含 Cars $1, 4$ 的连通分量。 下图展示了处理前 $11$ 个查询后车厢的情况。

标签: AtCoder|abc225D

来源

AtCoder|abc225D