在 JOI 共和国中，有 $N$ 个机场，编号从 $0$ 到 $N - 1$。共有 $N - 1$ 条航线，编号从 $0$ 到 $N - 2$。航线 $i$ ($0 \le i \le N - 2$) 双向连接机场 $U_i$ 和机场 $V_i$。通过连接多条航线，可以从任意机场到达其他任何机场。对于每个机场，最多有 $3$ 条航线将其与其他机场相连。

Benjamin 计划在 JOI 共和国进行一次旅行。在旅行的最后一天，他想到达温泉所在的机场。游乐园位于机场 $x$，温泉位于机场 $y$。由于 Benjamin 对航线一无所知，他将与航空公司的工作人员 Ali 进行交流。Benjamin 想知道从游乐园所在的机场到温泉所在的机场所需乘坐的最少航线数量。Ali 了解航线的信息，但 Benjamin 不知道他必须乘坐哪些航线。

1. Ali 为每个机场设置一个 ID 代码。ID 代码是一个介于 $0$ 到 $2N + 19$（含）之间的整数。
2. Benjamin 获取游乐园所在机场的 ID 代码 $X$，以及温泉所在机场的 ID 代码 $Y$。
3. Benjamin 向 Ali 发送一封电子邮件。消息是一个长度恰好为 $20$ 的字符串。消息中的每个字符均为 $0$ 或 $1$。
4. Ali 给 Benjamin 写一封信。信中包含一个长度在 $1$ 到 $300\,000$（含）之间的字符串。信中的每个字符均为 $0$ 或 $1$。

请编写程序来实现航空公司工作人员 Ali 的策略和旅行者 Benjamin 的策略。注意，在第 2 步中，Benjamin 可以获得游乐园和温泉所在机场的 ID 代码 $X, Y$。但是，Benjamin 无法获得机场编号 $x, y$。

实现细节

你需要提交两个文件。

第一个文件是 Ali.cpp。它应实现 Ali 的策略，并包含以下两个函数。程序应使用预处理指令 #include "Ali.h"。

• void Init(int N, std::vector<int> U, std::vector<int> V) 此函数实现 Ali 设置机场 ID 代码的策略。对于每个场景（详见“评分”部分），此函数会被调用恰好一次。

  • 参数 $N$ 是 JOI 共和国中机场的数量。
  • 参数 $U, V$ 是长度为 $N - 1$ 的数组。这意味着 $U[i], V[i]$ 是航线 $i$ ($0 \le i \le N - 2$) 连接的机场 $U_i, V_i$。

• std::string SendA(std::string S) 此函数实现 Ali 给 Benjamin 写信的策略。对于每个场景，此函数在调用 SendB（见下文）之后被调用恰好一次。

  • 参数 $S$ 是一个长度为 $20$ 的字符串，是 Benjamin 发送给 Ali 的电子邮件。
  • SendA 函数应返回一个字符串，这是 Ali 写给 Benjamin 的信。
  • 返回值应为一个长度在 $1$ 到 $300\,000$ 之间的字符串。如果不满足此条件，你的程序将被判为 Wrong Answer [5]。
  • 返回值的每个字符应为 $0$ 或 $1$。如果不满足此条件，你的程序将被判为 Wrong Answer [6]。

对于每次 Init 函数调用，以下函数应为每个机场各调用一次。总共应调用 $N$ 次。

• void SetID(int p, int value)
  • 参数 $p$ 表示 Ali 为机场 $p$ 设置 ID 代码。应满足 $0 \le p \le N - 1$。如果不满足此条件，你的程序将被判为 Wrong Answer [1]。
  • 参数 $value$ 是 Ali 为指定机场设置的 ID 代码。应满足 $0 \le value \le 2N + 19$。如果不满足此条件，你的程序将被判为 Wrong Answer [2]。
  • 不允许对同一个参数 $p$ 多次调用 SetID 函数。如果不满足此条件，你的程序将被判为 Wrong Answer [3]。
  • 当 Init 函数终止时，SetID 的调用次数应为 $N$。如果不满足此条件，你的程序将被判为 Wrong Answer [4]。

当 SetID 函数调用被判为 Wrong Answer 时，你的程序将立即终止。

第二个文件是 Benjamin.cpp。它应实现 Benjamin 的策略，并包含以下两个函数。程序应使用预处理指令 #include "Benjamin.h"。

• std::string SendB(int N, int X, int Y) 此函数实现 Benjamin 向 Ali 发送电子邮件的策略。对于每个场景，此函数在调用 Init 之后被调用恰好一次。

  • 参数 $N$ 是 JOI 共和国中机场的数量。
  • 参数 $X$ 是游乐园所在机场的 ID 代码。
  • 参数 $Y$ 是温泉所在机场的 ID 代码。
  • SendB 函数应返回一个字符串，即 Benjamin 发送给 Ali 的电子邮件。
  • 如果返回值不是长度为 $20$ 的字符串，你的程序将被判为 Wrong Answer [7]。
  • 返回值的每个字符应为 $0$ 或 $1$。如果不满足此条件，你的程序将被判为 Wrong Answer [8]。

• int Answer(std::string T) 此函数应计算 Benjamin 从机场 $x$ 到机场 $y$ 所需乘坐的最少航线数量。对于每个场景，此函数在调用 SendA 之后被调用恰好一次。

  • 参数 $T$ 是一个长度在 $1$ 到 $300\,000$ 之间的字符串，是 Ali 发送给 Benjamin 的信。
  • 此函数应返回 Benjamin 从机场 $x$ 到机场 $y$ 所需乘坐的最少航线数量。

重要提示

• 你的程序可以实现其他内部函数或使用全局变量。提交的文件将与评测程序一起编译，成为一个单一的可执行文件。所有全局变量和内部函数都应声明在匿名命名空间中，以避免与其他文件冲突。在评测时，它将作为 Ali 和 Benjamin 两个进程执行。Ali 的进程和 Benjamin 的进程不能共享全局变量。
• 你的程序不得使用标准输入和标准输出。你的程序不得通过任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。

评分

测试用例包含 $Q$ 个场景，编号从 $0$ 到 $Q - 1$。每个场景指定以下值。有关这些值的范围，请参阅“数据范围”。

• JOI 共和国中机场的数量 $N$。
• 游乐园所在机场的编号 $x$。
• 温泉所在机场的编号 $y$。
• 航线信息 $(U_0, V_0), (U_1, V_1), \dots, (U_{N-2}, V_{N-2})$。

对于每个场景，函数 Init, SendB, SendA, Answer 会被调用。你的程序应使用有效的参数调用相应的函数，并返回适当的值。这些函数按以下顺序调用：

1. 对于 $k = 0, 1, \dots, Q - 1$，按此顺序执行以下步骤 2-5。
2. 调用 Init 函数。参数设置为实现细节中指定的场景 $k$ 的参数。
3. 调用 SendB 函数。参数设置为实现细节中指定的场景 $k$ 的参数。
4. 调用 SendA 函数。参数设置为实现细节中指定的场景 $k$ 的参数。
5. 调用 Answer 函数。参数设置为实现细节中指定的场景 $k$ 的参数。

如果你的程序在这些过程中被判为 Wrong Answer，你的程序将立即终止，并被视为未通过该测试用例。

数据范围

• $1 \le Q \le 50$。
• $2 \le N \le 10\,000$。
• $0 \le U_i < V_i \le N - 1$ ($0 \le i \le N - 2$)。
• $0 \le x \le N - 1$。
• $0 \le y \le N - 1$。
• $x \neq y$。
• 可以通过连接多条航线从任意机场到达其他任何机场。
• 对于每个机场，最多有 $3$ 条航线将其与其他机场相连。

子任务

1. (15 分) $Q = 1$。
2. (85 分) $Q \ge 2$。

评分说明

如果你的程序在子任务 1 的任何场景中被判为 Wrong Answer，则该子任务得分为 0。 如果你的程序正确回答了子任务 1 的所有测试用例，则该子任务的得分计算如下。其中 $L_1$ 是 Ali 发送给 Benjamin 的字符串的最大长度。

如果你的程序在子任务 2 的任何场景中被判为 Wrong Answer，则该子任务得分为 0。 如果你的程序正确回答了子任务 2 的所有测试用例，则该子任务的得分计算如下。其中 $L_2$ 是 Ali 发送给 Benjamin 的字符串的最大长度。注意，如果 $1\,401 \le L_2$，则该子任务得分为 0。

样例

样例 1

1
4 0 2
0 1
1 2
2 3

样例 2

2
10 0 9
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
15 12 8
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14

说明

在样例 2 中，有 $Q = 2$ 个场景。 对于第一个场景，Answer 函数应返回 $9$。 对于第二个场景，Answer 函数应返回 $6$。