AT_abc225_d [ABC225D] Play Train

题目描述

高桥君正在用玩具火车进行连接和分离的游戏。
共有 $N$ 辆火车，分别命名为火车 $1$、火车 $2$、$\ldots$、火车 $N$。
一开始，所有火车都是分开的，互不连接。

现在有 $Q$ 个操作，请按给定顺序依次处理。
操作有以下 $3$ 种类型之一：

• 1 x y ：将火车 $x$ 的尾部与火车 $y$ 的头部连接。
  保证以下条件成立：
  • $x \neq y$
  • 在执行该操作前，火车 $x$ 的尾部没有连接其他火车
  • 在执行该操作前，火车 $y$ 的头部没有连接其他火车
  • 在执行该操作前，火车 $x$ 和火车 $y$ 属于不同的连通分量
• 2 x y ：将火车 $x$ 的尾部与火车 $y$ 的头部分离。
  保证以下条件成立：
  • $x \neq y$
  • 在执行该操作前，火车 $x$ 的尾部与火车 $y$ 的头部直接连接
• 3 x ：输出包含火车 $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$

设 $c_i=3$ 类型的操作共有 $q$ 个，请输出 $q$ 行。
第 $k$ 行输出第 $k$ 个此类操作的答案。

输入输出样例 #1

输入 #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

说明/提示

数据范围

• $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$

样例解释 1

处理到 $\mathrm{query}_5$ 时，火车的连接情况如下图所示。此时，例如火车 $2$ 与火车 $3,5,6,7$ 属于同一连通分量，但与火车 $1,4$ 不属于同一连通分量。

处理到 $\mathrm{query}_{11}$ 时，火车的连接情况如下图所示。

由 ChatGPT 4.1 翻译