魔法书被放哪了？

题目描述:

背景

在温州市魔法图书馆里，有 n 本魔法书，编号从 1 到 n， 同时也有 n 个书架，编号同样是 1 到 n。最初，第 i 个书架上摆放着编号为 i 的魔法书。但是图书馆里来一个捣蛋鬼，他会把编号a的魔法书放到编号b的书架上，或者把编号a跟编号b的书架上的书进行交换。然而今天管理员又非常得忙，没有时间去整理书架，你能告诉管理员编号a的魔法书在编号几的书架上吗？

会有 q 次操作，操作分为以下三种：

• 类型 1：`1 a b`，捣蛋鬼把编号为 a 的魔法书摆放到编号 b 的书架上。
• 类型 2：`2 a b`，捣蛋鬼交换了编号 a 和编号 b 书架上的所有魔法书。
• 类型 3：`3 a`，管理员向你询问编号为 a 的魔法书，它现在在编号几的书架上。

请你回答所有的询问。

输入格式:

第一行两个整数 n 和 q，表示魔法书的数量和操作次数。接下来 q 行，每行表示一个操作，格式如下：

• 若为类型 1，则输入三个整数 `1 a b`。
• 若为类型 2，则输入三个整数 `2 a b`。
• 若为类型 3，则输入两个整数 `3 a`。

输出格式:

对于每个类型 3 的操作，输出一行一个整数，表示编号 a 的魔法书所在书架的编号。

数据范围:

对于 30% 的数据，$1 \leq n , q \leq 1000$。

对于 100% 的数据，$1 \leq n,q \leq 10^6$，并保证至少会有一次操作 3。

保证所有操作合法，位置编号和书编号均在 1 到 n 之间。

样例输入:

(双击复制)

3 6
1 1 2
2 1 3
3 1
1 2 3
3 2
3 3

样例输出:

(双击复制)

2
3
1

时间限制: 1000ms
空间限制: 256MB

---

来源: 温州市计算机学会