#214564. [JOISC 2013] 星际飞船 / Spaceships

在宇宙遥远彼端的某个银河系中，存在 个拥有发达文明的星球。星球编号为 到 。每个星球管理着一艘宇宙飞船，飞船可能处于 正在前往其他星球 或 闲置 两种状态之一。当星球 管理的宇宙飞船正用于前往星球 时，该飞船会在星球 与 之间多次往返。飞船从星球 前往星球 时，普通旅客可乘船从 前往 ；但当飞船从星球 返回星球 时，由于燃料问题或装载货物等原因，普通旅客不可乘船。若星球 管理的宇宙飞船处于闲置状态，则该飞船在星球 待命。

目前所有宇宙飞船均处于闲置状态。未来的飞船状态变更计划已确定，变更类型如下：

• 将星球 管理的闲置宇宙飞船设置为前往星球 的状态。此操作仅当普通旅客无法通过多次乘船从星球 到达星球 时方可执行。
• 将星球 管理的正在使用的宇宙飞船设置为闲置状态。

计划在该银河系旅行的两人为安排会面计划，准备了若干如下形式的查询：

• 在计划的某一时刻，若一人位于星球 ，另一人位于星球 ，两人能否以普通旅客身份乘宇宙飞船会合？若能，在哪个星球会合所需乘船次数最少？即：是否存在星球 ，使得普通旅客可通过多次乘船从星球 到达 ，且从星球 到达 ？若存在，哪个星球 能使从 到 与从 到 的乘船次数之和最小？

作为优秀程序员的你，被要求解答两人的所有查询。

任务

给定按时间顺序排列的宇宙飞船状态变更计划与查询，编写程序回答所有查询。

从标准输入读取以下输入数据：

• 第 行包含以空格分隔的整数 ，表示星球数量为 ，状态变更次数与查询次数之和为 。
• 后续 行按时间顺序描述状态变更与查询。其中第 行（）包含 个或 个以空格分隔的整数。记第一个整数为 ，对应以下情况之一：

(i) 当 时：

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

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

(ii) 当 时：

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

保证 ，且此时星球 管理的宇宙飞船处于使用状态。

(iii) 当 时：

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

保证 ，，。

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

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

样例输入 1

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

样例输出 1

-1
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

限制

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

子任务

子任务 1 [10 分]

满足以下条件：

子任务 2 [30 分]

• 满足 ()

子任务 3 [60 分]

无额外限制

翻译由 DeepSeek V3 完成