题目描述

在宇宙遥远彼端的某个银河系中，存在 $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 \leq i \leq Q$）包含 $2$ 个或 $3$ 个以空格分隔的整数。记第一个整数为 $T_i$，对应以下情况之一：

(i) 当 $T_i = 1$ 时：

该行包含整数 $T_i, A_i, B_i$，表示以下状态变更：将星球 $A_i$ 管理的宇宙飞船设置为前往星球 $B_i$ 的状态。

保证 $1 \leq A_i \leq N$，$1 \leq B_i \leq N$，$A_i \neq B_i$，且此时星球 $A_i$ 管理的宇宙飞船处于闲置状态，且此时普通旅客无法通过多次乘船从星球 $B_i$ 到达星球 $A_i$。

(ii) 当 $T_i = 2$ 时：

该行包含整数 $T_i, A_i$，表示以下状态变更：将星球 $A_i$ 管理的宇宙飞船设置为闲置状态。

保证 $1 \leq A_i \leq N$，且此时星球 $A_i$ 管理的宇宙飞船处于使用状态。

(iii) 当 $T_i = 3$ 时：

该行包含整数 $T_i, A_i, B_i$，表示以下查询：此时若一人位于星球 $A_i$，另一人位于星球 $B_i$，两人能否以普通旅客身份乘宇宙飞船会合？若能，在哪个星球会合所需乘船次数最少？

保证 $1 \leq A_i \leq N$，$1 \leq B_i \leq N$，$A_i \neq B_i$。

输出格式

向标准输出针对每个查询依次输出一行：

• 若可以会合，输出使乘船次数最少的会合星球编号；
• 若无法会合，输出整数 $-1$。

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

-1
4

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

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

提示

限制

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

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

子任务

子任务 1 [10 分]

满足以下条件：

• $N \leq 5\,000$
• $Q \leq 5\,000$

子任务 2 [30 分]

• 满足 $T_i \neq 2$ ($1 \leq i \leq Q$)

子任务 3 [60 分]

无额外限制

翻译由 DeepSeek V3 完成