P14443 [JOISC 2013] 星际飞船 / Spaceships

在宇宙遥远彼端的某个银河系中，存在 $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$。

### 限制 所有输入数据满足以下条件： - $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 完成