#ABC395D. 鸽巢互换

鸽巢互换

AT_abc395_d [ABC395D] 鸽巢互换

题目描述

\hspace{15pt}有 nn 只标记为 1,2,…,n1, 2, \dots, n 的鸽子,以及 nn 个标记为 1,2,…,n1, 2, \dots, n 的巢。最初,鸽子 i(1≦i≦n)i \left(1 \leqq i \leqq n\right) 在巢 ii 中。

\hspace{15pt}你将对这些鸽子依次执行 qq 次操作。操作共有三种类型:

∙ \hspace{23pt}\bullet\,类型 11:给定整数 aa 和 $b \left(1 \leqq a \leqq n;\ 1 \leqq b \leqq n\right)$,将鸽子 aa 从其当前所在的巢中取出,并移动到巢 bb;

∙ \hspace{23pt}\bullet\,类型 22:给定整数 aa 和 b(1≦a<b≦n)b \left(1 \leqq a < b \leqq n\right),将巢 aa 中的所有鸽子移动到巢 bb,并将巢 bb 中的所有鸽子移动到巢 aa,这两个移动同时发生;

∙ \hspace{23pt}\bullet\,类型 33:给定整数 a(1≦a≦n)a \left(1 \leqq a \leqq n\right),鸽子 aa 报告它当前所在的巢的编号。

\hspace{15pt}请按操作给出的顺序,输出每个类型 33 操作的结果。

输入格式

\hspace{15pt}第一行输入两个整数 $n, q \left(1 \leqq n \leqq 10^6;\ 1 \leqq q \leqq 3 \times 10^5\right)$ 代表鸽子和鸽巢的数量,以及操作的次数。

\hspace{15pt}此后 qq 行,第 ii 行输入第 ii 次操作,格式为以下三种之一:

∙ \hspace{23pt}\bullet\,若为类型 11 操作,输入三个整数 1,a,b(1≦a,b≦n)1, a, b \left(1 \leqq a, b \leqq n\right);

∙ \hspace{23pt}\bullet\,若为类型 22 操作,输入三个整数 2,a,b(1≦a<b≦n)2, a, b \left(1 \leqq a < b \leqq n\right);

∙ \hspace{23pt}\bullet\,若为类型 33 操作,输入两个整数 3,a(1≦a≦n)3, a \left(1 \leqq a \leqq n\right)。

\hspace{15pt}保证所有操作都是合法的,且至少存在一次类型 33 的操作。

输出格式

\hspace{15pt}设类型 33 操作的数量为 cc。输出 cc 行,第 ii 行输出一个整数,代表第 ii 次类型 33 操作中鸽子报告的巢的编号。

测试样例

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 解释

\hspace{15pt}在给定的操作中,鸽子的移动如下图所示:

\hspace{15pt}各次类型 33 操作报告的巢号依次为 4,5,2,54, 5, 2, 5。

样例 2 解释

\hspace{15pt}类型 11 操作的目标巢可能与鸽子当前所在的巢相同。