[AdditionalFile5123.zip](file://AdditionalFile5123.zip?type=additional_file)

#5123. 「JOISC 2013 Day4」宇宙飞船

标签: 传统 | 时间限制: 10000 ms | 内存限制: 256 MiB |

题目描述

题目译自 JOISC 2013 Day4 T3 「宇宙船」

在宇宙的遥远彼方，某个星系中有 $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$；若存在，找出使从 $a$ 到 $c$ 和从 $b$ 到 $c$ 搭乘飞船次数总和最小的星球 $c$。

作为一名优秀的程序员，你需要回答这两个人提出的所有问题。

给定未来飞船状态变更的日程和按时间顺序排列的问题，你需要编写一个程序回答这些问题。

输入格式

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

• 第一行包含两个整数 $N, Q$，用空格分隔，表示星球数量为 $N$，状态变更和问题总次数为 $Q$。
• 接下来 $Q$ 行按时间顺序描述状态变更和问题。第 $i$ $(1 \leq i \leq Q)$ 行包含 $2$ 个或 $3$ 个整数，用空格分隔。设第一个整数为 $T_{i}$，则有以下情况：

1. 若 $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}$。
2. 若 $T_{i}=2$： 该行包含两个整数 $T_{i}, A_{i}$，表示状态变更：将星球 $A_{i}$ 管理的飞船变更为闲置状态。 保证 $1 \leq A_{i} \leq N$，且此时星球 $A_{i}$ 管理的飞船为使用中状态。
3. 若 $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$。

样例 1

输入

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

输出

-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

输出

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

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 1000000$
• $1 \leq Q \leq 1000000$

详细子任务附加限制及分值如下表所示。