在遥远的宇宙中，有一个文明高度发达的银河系，其中有 $N$ 个星球，编号为 $1$ 到 $N$。每个星球都管理着一艘宇宙船。宇宙船处于“用于前往其他星球”的状态，或者“未使用”的状态。当星 $a$ 管理的宇宙船处于前往星 $b$ 的状态时，该宇宙船会在星 $a$ 和星 $b$ 之间往返多次。当宇宙船从星 $a$ 前往星 $b$ 时，普通乘客可以乘坐宇宙船从星 $a$ 前往星 $b$；但由于燃料问题或装载货物等原因，当宇宙船从星 $b$ 返回星 $a$ 时，普通乘客无法乘坐。此外，当星 $a$ 管理的宇宙船处于未使用状态时，该宇宙船停留在星 $a$。

目前，所有宇宙船都处于未使用状态。未来宇宙船状态变更的计划已经确定。状态变更分为以下几种：

• 将处于未使用状态的星 $a$ 管理的宇宙船，变为前往星 $b$ 的使用状态。注意，这仅在普通乘客无法通过多次乘坐宇宙船从星 $b$ 前往星 $a$ 时才会发生。
• 将处于使用状态的星 $a$ 管理的宇宙船，变为未使用状态。

计划在该银河系旅行的两个人为了安排会面，准备了以下形式的问题：

• 在计划的某个时刻，假设一人在星 $a$，另一人在星 $b$，两人是否能作为普通乘客利用宇宙船会合？如果可以会合，在哪个星球会合能使宇宙船的使用次数最少？也就是说，是否存在一个星 $c$，使得普通乘客可以通过多次乘坐宇宙船从星 $a$ 前往星 $c$，且也能从星 $b$ 前往星 $c$？如果存在，在所有满足条件的星 $c$ 中，哪一个能使从星 $a$ 到星 $c$ 的宇宙船使用次数与从星 $b$ 到星 $c$ 的宇宙船使用次数之和最小？

你需要编写一个程序，在给定宇宙船状态变更计划和问题序列的情况下，回答所有问题。

输入格式

从标准输入读取以下内容：

• 第 $1$ 行包含两个整数 $N$ 和 $Q$，分别表示星球的数量 $N$，以及状态变更次数与问题数量的总和 $Q$。

• 接下来的 $Q$ 行按时间顺序表示状态变更和问题。第 $i$ 行 ($1 \le i \le Q$) 包含 $2$ 个或 $3$ 个以空格分隔的整数。设第一个整数为 $T_i$，则有以下几种情况：

  (i) 当 $T_i = 1$ 时： 该行包含整数 $T_i, A_i, B_i$，表示以下状态变更：将星 $A_i$ 管理的宇宙船变为前往星 $B_i$ 的使用状态。 保证 $1 \le A_i \le N, 1 \le B_i \le N, A_i \neq B_i$，此时星 $A_i$ 管理的宇宙船处于未使用状态，且此时普通乘客无法通过多次乘坐宇宙船从星 $B_i$ 前往星 $A_i$。

  (ii) 当 $T_i = 2$ 时： 该行包含整数 $T_i, A_i$，表示以下状态变更：将星 $A_i$ 管理的宇宙船变为未使用状态。 保证 $1 \le A_i \le N$，且此时星 $A_i$ 管理的宇宙船处于使用状态。

  (iii) 当 $T_i = 3$ 时： 该行包含整数 $T_i, A_i, B_i$，表示以下问题：在此刻，假设一人在星 $A_i$，另一人在星 $B_i$，两人是否能作为普通乘客利用宇宙船会合？如果可以会合，在哪个星球会合能使宇宙船的使用次数最少？ 保证 $1 \le A_i \le N, 1 \le B_i \le N, A_i \neq B_i$。

输出格式

对于每个问题，按顺序各占一行输出：

• 如果可以会合，输出使宇宙船使用次数最少的会合星球编号。
• 如果无法会合，输出整数 $-1$。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 1\,000\,000$
• $1 \le Q \le 1\,000\,000$

子任务

子任务 1 [10 点] 满足以下条件： $N \le 5\,000$ $Q \le 5\,000$

子任务 2 [30 点] * 满足 $T_i \neq 2$ ($1 \le i \le Q$)。

子任务 3 [60 点] 无额外限制。

样例

输入格式 1

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

输出格式 1

-1
4

说明

在此例中，状态变更和问题按顺序如下： 星 $2$ 管理的宇宙船变为前往星 $4$ 的使用状态。 此时若两人分别在星 $2$ 和星 $6$，无法会合，因此输出 $-1$。 星 $4$ 管理的宇宙船变为前往星 $3$ 的使用状态。 星 $6$ 管理的宇宙船变为前往星 $4$ 的使用状态。 * 此时若两人分别在星 $2$ 和星 $6$，可以在星 $3$ 或星 $4$ 会合。为了使宇宙船使用次数最少，应在星 $4$ 会合，因此输出 $4$。

输入格式 2

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

输出格式 2

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6