#P0813. 链式机器人
链式机器人
题目描述
化工科技有限公司正在研发一款可组合的航天机器人系统。系统由 个独立的机器人模块组成,编号分别为 。每个模块前端和后端都预留有标准化的对接接口,初始时,所有模块均处于分离状态。
你需要处理 次操作,每次操作有以下三种类型:
-
1 x y:将模块 的前端对接到模块 的后端。- 保证对接前,模块 的后端没有模块连接,模块 的前端也没有模块连接;
- 保证对接前,模块 与模块 不属于同一机器人链(即当前不连通)。
-
2 x y:将模块 的前端与模块 的后端断开连接。- 保证断开前,模块 的前端正连接在模块 的后端。
-
3 x:查询模块 所在的机器人链,并按从前到后的顺序输出这条链上所有模块编号。
你需要按顺序执行所有操作,并对所有类型为 3 的操作输出结果。
输入格式
第一行包含两个整数 和 ,表示模块总数和操作次数;
接下来 行,每行表示一次操作,格式如下:
- 若为连接操作,则为
1 x y; - 若为断开操作,则为
2 x y; - 若为查询操作,则为
3 x。
所有输入均满足题目描述中的条件,保证,保证格式为3 x的操作要求输出的模块编号总数不超过个。
输出格式
对于每一个查询操作 3 x,第一行输出一个整数,表示模块所在的机器人链中的模块总数。
第二行输出个整数,从前往后输出该链中所有的模块编号。
样例
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
提示
下图展示了处理前个操作时的模块状态。
例如,模块与模块属于同一机器人链,而该链与包含模块的链不同。
下图展示了处理前个操作时的模块状态。