JOI-kun 有一个妹妹 IOI-chan。JOI-kun 正在名为 JOIOI 公园的游乐园里和 IOI-chan 一起玩耍。

JOIOI 公园里有 $N$ 个景点，编号从 $0$ 到 $N-1$。此外，公园里还有 $M$ 条路径。每条路径都可以双向通行。每条路径连接两个不同的景点。通过一条或多条路径，可以从任意一个景点到达其他任何景点。由于 JOI-kun 和 IOI-chan 拥有 JOIOI 公园的地图，他们知道景点之间是如何通过路径连接的。

每个景点都有一个留言板。在每个留言板上，JOI-kun 只能写一个整数，即 $0$ 或 $1$。他可以在不同的留言板上写不同的整数。一旦他在留言板上写下了一个整数，它就不会被其他游客覆盖。

JOI-kun 和 IOI-chan 想要在不同的景点玩耍。因此，他们会先分开玩一段时间，然后在某个地方会合。由于他们没有手机等通讯工具，JOI-kun 决定利用留言板向 IOI-chan 传达一个整数 $X$，该整数描述了会合的时间。

具体来说，JOI-kun 和 IOI-chan 将通过以下方式进行交流： 首先，JOI-kun 在每个留言板上写下一个整数，$0$ 或 $1$。 然后，IOI-chan 重复地从一个景点移动到另一个通过路径相连的景点。在此过程中，她会读取她访问的每个景点（包括她初始所在景点的留言板）的留言板上所写的整数。

通过少量的移动，IOI-chan 想要知道 JOI-kun 想要传达的整数 $X$。

任务

编写两个程序，使 JOI-kun 能够将整数 $X$ 传达给 IOI-chan。

• 给定 JOIOI 公园的路径信息和整数 $X$，第一个程序决定 JOI-kun 将在每个留言板上写的整数（$0$ 或 $1$）。
• 给定 JOIOI 公园的路径信息、IOI-chan 的初始景点位置以及 JOI-kun 在初始景点留言板上写的整数，第二个程序通过在景点之间移动并读取目的地留言板上的整数，计算出整数 $X$。

请注意，两个程序将获得关于 JOIOI 公园路径的完全相同的信息。特别是，给两个程序的景点编号是相同的。此外，给两个程序的路径顺序也是相同的。

实现细节

你需要提交两个文件。

第一个文件是 Joi.cpp。该文件实现 JOI-kun 的策略，并实现以下函数。程序应包含 Joi.h。

• void Joi(int N, int M, int A[], int B[], long long X, int T)

对于每个测试用例，此函数仅被调用一次。 参数 $N$ 是 JOIOI 公园中景点的数量。 参数 $M$ 是连接景点的路径数量。 参数 $A[]$、$B[]$ 是长度为 $M$ 的序列，描述了连接景点的路径信息。元素 $A[i], B[i]$ ($0 \le i \le M-1$) 表示有一条路径直接连接景点 $A[i]$ 和景点 $B[i]$。 参数 $X$ 是 JOI-kun 想要传达的整数。 * 参数 $T$ 是测试用例的子任务编号。

你的程序应调用以下函数：

• void MessageBoard(int attr, int msg)

此函数向留言板写入一个整数。 参数 attr 是留言板所在景点的编号。attr 应该是一个大于或等于 $0$ 且小于或等于 $N-1$ 的整数。如果不满足，你的程序将被视为 Wrong Answer[1]。你的程序不能使用相同的参数 attr 调用此函数。如果此函数使用相同的参数 attr 调用了两次，你的程序将被视为 Wrong Answer[2]。 参数 msg 是将要写在景点 attr 留言板上的整数。msg 是一个 $0$ 或 $1$ 的整数。如果不满足，你的程序将被视为 Wrong Answer[3]。

你的程序必须恰好调用 MessageBoard 函数 $N$ 次。当 Joi 函数终止时，如果调用 MessageBoard 函数的次数与 $N$ 不同，你的程序将被视为 Wrong Answer[4]。

如果 Joi 的函数调用被视为无效，你的程序将被终止。

第二个文件是 Ioi.cpp。该文件实现 IOI-chan 的策略，并实现以下函数。程序应包含 Ioi.h。

• long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)

对于每个测试用例，此函数仅被调用一次。 参数 $N$ 是 JOIOI 公园中景点的数量。 参数 $M$ 是连接景点的路径数量。 参数 $A[]$、$B[]$ 是长度为 $M$ 的序列，描述了连接景点的路径信息。元素 $A[i], B[i]$ ($0 \le i \le M-1$) 表示有一条路径直接连接景点 $A[i]$ 和景点 $B[i]$。 参数 $P$ 是 IOI-chan 的初始景点编号。 参数 $V$ 是 JOI-kun 在景点 $P$ 的留言板上写的整数。 参数 $T$ 是测试用例的子任务编号。

传递给 Ioi 函数的参数 $N, M, A[], B[], T$ 与传递给 Joi 函数的参数相同。

Ioi 函数应返回 JOI-kun 想要传达的整数（即传递给 Joi 函数的参数 $X$）。如果返回了不同的值，你的程序将被视为 Wrong Answer[5]。

你的程序可以调用以下函数：

• int Move(int dest)

此函数描述 IOI-chan 的移动。 参数 dest 是 IOI-chan 要前往的景点编号。dest 应该是一个大于或等于 $0$ 且小于或等于 $N-1$ 的整数。如果不满足，你的程序将被视为 Wrong Answer[6]。景点 dest 应该与 IOI-chan 当前所在的景点通过路径直接相连。如果不满足，你的程序将被视为 Wrong Answer[7]。 此函数的返回值是 JOI-kun 在景点 dest 的留言板上写的整数。

你的程序调用 Move 函数的次数不能超过 $20\,000$ 次。如果不满足，你的程序将被视为 Wrong Answer[8]。

重要提示

• 你的程序可以实现其他内部使用的函数，或使用全局变量。提交的程序将与评测程序一起编译，并成为一个单一的可执行文件。所有全局变量和内部函数都应声明为 static，以避免与其他文件冲突。由于 JOI-kun 和 IOI-chan 的程序在评测时作为两个不同的进程执行，它们不能共享全局变量。
• 你的程序不应使用标准输入和标准输出。你的程序不应以任何方式与其他文件通信。

样例通信

以下是评测程序的一个样例输入及对应的函数调用。请注意，由于样例输入较大，此处仅展示部分内容。完整的样例输入请参考比赛网站上的 sample-01.txt。

Joi(...) 和 Ioi(...) 的参数如下：

数据范围

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

• $60 \le N \le 10\,000$
• $1 \le M \le 20\,000$
• $0 \le A[i] \le N-1$ ($0 \le i \le M-1$)
• $0 \le B[i] \le N-1$ ($0 \le i \le M-1$)
• $A[i] \neq B[i]$ ($0 \le i \le M-1$)
• $(A[i], B[i]) \neq (A[j], B[j])$ ($0 \le i < j \le M-1$)
• $(A[i], B[i]) \neq (B[j], A[j])$ ($0 \le i < j \le M-1$)
• 可以通过一条或多条路径从任意景点到达其他任何景点。
• $0 \le X \le 2^{60} - 1$
• $0 \le P \le N-1$

子任务

共有 5 个子任务。各子任务的分数和附加限制如下：

子任务 1 [8 分]

• $T = 1$
• $N \le 300$

子任务 2 [10 分]

• $T = 2$

子任务 3 [10 分]

• $T = 3$
• $M = N - 1$
• $A[i] = i, B[i] = i + 1$ ($0 \le i \le N - 2$)
• 你的程序调用 Move 函数的次数不能超过 $250$ 次。

子任务 4 [55 分]

• $T = 4$
• $240 \le N$

此子任务的分数计算如下： 令 $C$ 为你的程序在此子任务中每个测试用例调用 Move 函数的最大次数。 此子任务的分数为： 如果 $960 < C$，则为 $0$ 分。 如果 $120 < C \le 960$，则为 $\lfloor 55 - 13 \log_2 (\frac{C}{120}) \rfloor$ 分。（此处 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。） * 如果 $C \le 120$，则为 $55$ 分。

请注意，当 $960 < C$ 时，在评测系统中，此子任务的详细信息可能是“Correct : 0 point”或“Incorrect”。

子任务 5 [17 分]

• $T = 5$
• 你的程序调用 Move 函数的次数不能超过 $120$ 次。