#ABC395D. 鸽巢互换
鸽巢互换
AT_abc395_d [ABC395D] 鸽巢互换
题目描述
有 只标记为 的鸽子,以及 个标记为 的巢。最初,鸽子 在巢 中。
你将对这些鸽子依次执行 次操作。操作共有三种类型:
类型 :给定整数 和 $b \left(1 \leqq a \leqq n;\ 1 \leqq b \leqq n\right)$,将鸽子 从其当前所在的巢中取出,并移动到巢 ;
类型 :给定整数 和 ,将巢 中的所有鸽子移动到巢 ,并将巢 中的所有鸽子移动到巢 ,这两个移动同时发生;
类型 :给定整数 ,鸽子 报告它当前所在的巢的编号。
请按操作给出的顺序,输出每个类型 操作的结果。
输入格式
第一行输入两个整数 $n, q \left(1 \leqq n \leqq 10^6;\ 1 \leqq q \leqq 3 \times 10^5\right)$ 代表鸽子和鸽巢的数量,以及操作的次数。
此后 行,第 行输入第 次操作,格式为以下三种之一:
若为类型 操作,输入三个整数 ;
若为类型 操作,输入三个整数 ;
若为类型 操作,输入两个整数 。
保证所有操作都是合法的,且至少存在一次类型 的操作。
输出格式
设类型 操作的数量为 。输出 行,第 行输出一个整数,代表第 次类型 操作中鸽子报告的巢的编号。
测试样例
6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2
4
5
2
5
1 2
1 1 1
3 1
1
30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8
3
15
7
样例 1 解释
在给定的操作中,鸽子的移动如下图所示:
各次类型 操作报告的巢号依次为 。
样例 2 解释
类型 操作的目标巢可能与鸽子当前所在的巢相同。