题目描述

题目译自 PA 2019 Runda 5 Sonda

这是一道交互题。

有一个 $n$ 个点的无向连通图。你有一个探测器，它最初在 $1$ 号节点。

你每次可以向探测器发送指令，给出节点 $v$，如果当前节点和 $v$ 之间有一条边，那么探测器就会移动到该节点，每次发出这一指令就会得到反馈信息。若探测器进行了移动并且这是探测器第偶数次移动，那么返回「成功」，否则返回「失败」。你最多可以发送 $10^6$ 次该指令。

你还另外需要进行 $n$ 次标记操作，需要保证恰好在机器人位于每个节点的时候进行一次标记操作。

交互方式

您的程序需要引用交互库：

#include "sonlib.h"

这个交互库提供以下函数：

int GetN()

• 返回一个正整数 $n(3\le n\le 400)$，表示这个图的节点数。

int GetSubtask()

• 返回一个整数 $s(0\le s\le 3)$，表示子任务类型。
  • 若 $s=0$，则表示该图没有任何附加性质；
  • 若 $s=1$，表示图为完整的二分图，即可以将点集划分为两非空集合 $A,B$，每个点都属于 $A$ 或 $B$ 中的一个，并且有 $|A|\cdot |B|$ 条边；
  • 若 $s=2$，保证图中 $1$ 与 $2$，$2$ 与 $3$，$3$ 与 $1$ 之间一定有边；
  • 若 $s=3$，保证图中所有点恰好与两个点相连。

int MoveProbe(int v)

• 向探测器发出「走向节点 $v$」的指令，如果探测器当前就在节点 $v$，你的程序会被直接判为错误。若探测器进行了移动并且这是探测器第偶数次移动，那么返回 1，否则返回 0，若探测器没有进行移动，也返回 0。

void Examine()

• 让探测器标记当前节点。如果该节点已经被标记，你的程序会被直接判为错误。当完成了所有节点的标记操作后，程序会被判定为正确并自动退出。

你需要实现主函数

int main()

样例

样例输入

4 4 0
1 2
2 3
3 1
2 4

样例交互过程