#P0813. 链式机器人

链式机器人

题目描述

化工科技有限公司正在研发一款可组合的航天机器人系统。系统由 nn 个独立的机器人模块组成,编号分别为 1、2、…、n1、2、…、n。每个模块前端和后端都预留有标准化的对接接口,初始时,所有模块均处于分离状态。

你需要处理 qq 次操作,每次操作有以下三种类型:

  • 1 x y:将模块 yy 的前端对接到模块 xx 的后端。

    • 保证对接前,模块 xx 的后端没有模块连接,模块 yy 的前端也没有模块连接;
    • 保证对接前,模块 xx 与模块 yy 不属于同一机器人链(即当前不连通)。
  • 2 x y:将模块 yy 的前端与模块 xx 的后端断开连接。

    • 保证断开前,模块 yy 的前端正连接在模块 xx 的后端。
  • 3 x:查询模块 xx 所在的机器人链,并按从前到后的顺序输出这条链上所有模块编号。

你需要按顺序执行所有操作,并对所有类型为 3 的操作输出结果。

输入格式

第一行包含两个整数 n(2≤n≤105)n(2 \le n \le 10^5) 和 q(1≤q≤105)q(1 \le q \le 10^5),表示模块总数和操作次数;

接下来 qq 行,每行表示一次操作,格式如下:

  • 若为连接操作,则为 1 x y;
  • 若为断开操作,则为 2 x y;
  • 若为查询操作,则为 3 x。

所有输入均满足题目描述中的条件,保证1≤x≤n,1≤y≤n1 \le x \le n, 1\le y \le n,保证格式为3 x的操作要求输出的模块编号总数不超过10610^6个。

输出格式

对于每一个查询操作 3 x,第一行输出一个整数mm,表示模块xx所在的机器人链中的模块总数。

第二行输出mm个整数,从前往后输出该链中所有的模块编号。

样例

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

提示

下图展示了处理前55个操作时的模块状态。

例如,模块22与模块3,5,6,73,5,6,7属于同一机器人链,而该链与包含模块1,41,4的链不同。

img

下图展示了处理前1111个操作时的模块状态。

img