B. 空间站调度

题目描述

在银河联邦的星际物流网络中，有 $n$ 艘运输飞船（编号从 $1$ 到 $n$）和 $n$ 个空间站（编号从 $1$ 到 $n$）。初始状态时，飞船 $i$ 停靠在空间站 $i$。中央控制系统会处理 $q$ 条操作指令，包含三种核心指令类型：

1. 1 a b：将飞船 $a$ 从当前空间站移动到空间站 $b$ ($1 \le a, b \le n$)。
2. 2 a b：同时交换空间站 $a$ 和空间站 $b$ 内的所有飞船，交换操作为原子操作，无先后顺序 ($1 \le a < b \le n$)。
3. 3 a：输出飞船 $a$ 当前所在的空间站编号。

输入格式

第一行输入两个整数 $n$，$q$，分别表示飞船数量，操作指令数量。

接下来 $q$ 行，每行输入一条操作指令，指令格式如上。

输出格式

对于操作 $3$，输出一个整数，表示答案。

样例输入1

6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2

样例输出1

4
5
2
5

数据范围

• 对于 $10\%$ 的数据，$1 \le n \le 10$，$1 \le q \le 10$。
• 对于 $50\%$ 的数据，$1 \le n \le 10^3$，$1 \le q \le 10^3$。
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le q \le 3 \times 10^5$。
• 所有操作都是以上三种操作之一。
• 所有操作都是合法的。
• 样例中至少有一个操作 $3$。
• 所有输入都是整数。