巴伊特太空署（Bajtocka Agencja Kosmiczna）几年前发现了小行星 BA-1T。巴伊塔扎（Bajtazar）负责监督一项无人探测任务，旨在将该行星上的矿物样本带回地球。不幸的是，由于软件开发人员的疏忽，探测器系统中存在许多错误，导致与探测器的通信变得非常困难。尽管如此，巴伊塔扎仍必须完成这项任务。
巴伊塔扎在小行星上确定了 $n$ 个关键点，需要从中采集矿物样本。这些点用 $1$ 到 $n$ 的自然数编号，探测器最初位于 $1$ 号点。这些点之间存在一定数量的双向连接。如果探测器位于连接的一端，它可以移动到另一端。不幸的是，有关连接的信息被编码在探测器中，而巴伊塔扎并不知晓。幸运的是，他记得探测器可以从任何点到达任何其他点，可能需要经过其他中间点。
理论上，事情很简单。巴伊塔扎可以向探测器发出移动到任何其他点的指令，探测器应告知巴伊塔扎移动是否成功。
然而，在实践中，由于软件错误，情况变得有些复杂。首先，如果巴伊塔扎指示移动到探测器当前所在的点，设备将会爆炸，导致研究无法进行。如果与目标点之间不存在直接连接，探测器将不会改变位置，巴伊塔扎会收到否定响应。如果连接存在，探测器将移动到该点。但由于另一个软件错误，巴伊塔扎只有在探测器执行了偶数次成功移动时才会收到肯定响应。否则，他将收到否定响应——与不存在连接时的响应完全相同。
探测器还可以检查其当前所在的点（即收集矿物样本）。为了保持研究的有序性，每个点必须且只能被检查一次。
由于探测器距离地球很远，发送指令非常耗时，因此巴伊塔扎最多只能发送一百万次移动指令。
请帮助巴伊塔扎完成研究，并恢复太空署对任务的信心！
交互方式
本题为交互题。你需要编写一个程序，通过提供的库与探测器进行通信。为此，请使用以下指令包含头文件 sonlib.h：
#include "sonlib.h"该库提供以下函数：
int GetN()– 返回参数 $n$ ($3 \le n \le 400$)，即小行星上关键点的数量。int GetSubtask()– 返回参数 $s$ ($0 \le s \le 3$)，详见下文“子任务”部分。int MoveProbe(int v)– 指示探测器移动到点 $v$。随后：- 如果未满足 $1 \le v \le n$ 的条件、探测器已位于点 $v$ 或程序之前已调用过 $1\,000\,000$ 次
MoveProbe，则程序将被终止，测试结果为错误。 - 如果当前点与 $v$ 之间不存在连接，探测器不会移动，函数返回 $0$。
- 如果连接存在，探测器将移动到点 $v$。如果这是探测器执行的第偶数次成功移动（例如第 2 次或第 10 次），函数返回 $1$。否则，函数返回 $0$。
- 如果未满足 $1 \le v \le n$ 的条件、探测器已位于点 $v$ 或程序之前已调用过 $1\,000\,000$ 次
void Examine()– 指示探测器检查其当前所在的点。随后：- 如果探测器尝试检查一个已经检查过的点，程序将被终止，测试结果为错误。
- 如果探测器已检查过每个点且仅检查过一次，库将终止程序并判定解决方案正确。
库通过调用 exit(0) 来终止程序。
探测器初始位于点 $1$。连接允许访问所有点（图是连通的）。连接在程序运行开始时即已确定，即库不会根据之前的查询更改连接。
严禁任何试图影响评测库内部运作的行为。
子任务
在所有测试中，$3 \le n \le 400$。你的程序最多可以调用 MoveProbe 函数 $1\,000\,000$ 次。
部分分数可以通过解决特定图结构的子任务获得。函数 GetSubtask 返回的参数 $s$ 可用于识别这些子任务：
- 如果 $s = 0$，图不需要满足任何额外假设。
- 如果 $s = 1$，连接图是一个完全二分图。点集可以划分为两个（未知的）非空子集 $A$ 和 $B$。存在 $|A| \cdot |B|$ 条连接，每条连接连接 $A$ 中的一个点和 $B$ 中的一个点。
- 如果 $s = 2$，保证存在三条特定连接：$(1, 2)$、$(2, 3)$ 和 $(3, 1)$。
- 如果 $s = 3$，每个点恰好与另外两个点相连。
你可以假设同一测试组内的每个测试用例具有相同的 $s$ 值。
样例
样例 1
GetN()
4
样例 2
GetSubtask()
0
说明
在示例测试中，存在以下连接：$(1, 2), (1, 3), (2, 3), (2, 4)$。注意，在此测试中 $s$ 可能为 $0$ 或 $2$。
| 调用函数 | 返回值 | 探测器新位置 | 成功移动次数 | 说明 |
|---|---|---|---|---|
GetN() |
4 | 1 | 0 | 共有 4 个关键点。 |
GetSubtask() |
0 | 1 | 0 | 参数 $s$ 为 0。 |
Examine() |
— | 1 | 0 | 检查点 1。 |
MoveProbe(4) |
0 | 1 | 0 | 点 1 与点 4 无连接。 |
MoveProbe(2) |
0 | 2 | 1 | 探测器移动。这是第 1 次成功移动（奇数）。 |
MoveProbe(3) |
1 | 3 | 2 | 第 2 次成功移动（偶数）。 |
Examine() |
— | 3 | 2 | 检查点 3。 |
MoveProbe(2) |
0 | 2 | 3 | |
Examine() |
— | 2 | 3 | 检查点 2。 |
MoveProbe(4) |
1 | 4 | 4 | |
Examine() |
— | — | — | 所有点均已检查。程序结束，测试通过。 |
巴伊塔扎总共执行了 5 次 MoveProbe 指令，未超过 $1\,000\,000$ 次的限制。
详细实现
示例错误解决方案和示例库可在 SIO 的“文件”部分找到。库的行为可能与用于评测的库不同，仅用于展示交互方式。
解决方案 son.cpp 可以通过以下方式编译：
g++ -O3 -static -o son son.cpp sonlib.cpp -std=c++17请确保 sonlib.h 和 sonlib.cpp 与你的解决方案位于同一文件夹中。
编译后，库通过标准输入读取图信息。输入的第一行应包含三个数字 $n, m, s$，分别表示关键点数量、连接数量和子任务编号。接下来的 $m$ 行，每行包含两个数字，表示连接的两个端点。示例测试对应的输入文件为 son0.in。