题目背景

请使用 C++ 20 提交。

不要引入头文件，并在文件头加入以下内容：

void SetID(int, int);

题目描述

在 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)
  该函数用于为每个机场设置 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$ 表示为机场 $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)
  该函数应计算从机场 $x$ 到机场 $y$ 的最少乘坐航线数（见「评分」中的场景说明），在 SendA 调用之后、每个场景调用 恰好一次。
  • 参数 $T$ 为 Ali 发给 Benjamin 的回信字符串，长度在 $1$ 到 $300\,000$（含）之间。
  • 函数应返回从机场 $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，程序将立即终止，并视为未通过该测试用例。

编译与本地测试

你可以从竞赛网页下载包含样例评测器的压缩包，用于本地测试。压缩包中也包含你程序的样例源文件。

样例评测器文件名为 grader.cpp。为测试你的程序，请将 grader.cpp、Ali.cpp、Benjamin.cpp、Ali.h、Benjamin.h 放在同一目录下，并运行以下命令进行编译：

g++ -std=gnu++17 -O2 -o grader grader.cpp Ali.cpp Benjamin.cpp

若编译成功，将生成可执行文件 grader。

注意：实际评测器与样例评测器不同。样例评测器作为单进程执行，从标准输入读取数据并向标准输出写出结果。

输入格式

样例评测器从标准输入读取如下数据。所有输入值均为整数。

$Q$
（场景 $0$ 的输入）
（场景 $1$ 的输入）
$\vdots$
（场景 $Q - 1$ 的输入）

每个场景的输入格式如下：

$N$ $x$ $y$
$U_0$ $V_0$
$U_1$ $V_1$
$\vdots$
$U_{N - 2}$ $V_{N - 2}$

输出格式

如果程序被判为 Wrong Answer [1]–[8] 中的任意一种，样例评测器会输出其类型（引号仅为说明）：“Wrong Answer [1]”。

否则，对每个场景，它会输出函数 Answer 的返回值以及 Ali 发给 Benjamin 的字符串的最大长度。样例评测器 不会 检查 Answer 的返回值是否正确。

Scenario 0: Your Answer = 3
Scenario 1: Your Answer = 1
Scenario 2: Your Answer = 4
Scenario 3: Your Answer = 1
Scenario 4: Your Answer = 5
Accepted: Maximum Length = 24

如果你的程序同时满足多种 Wrong Answer 的判定条件，样例评测器只报告其中一种。此外，即使你的程序在后续场景被判为 Wrong Answer [1]–[8]，只要在第一个场景未被判错，样例评测器也可能先输出如下中间结果：

Scenario 0: Your Answer = 3
Scenario 1: Your Answer = 1
Scenario 2: Your Answer = 4
Wrong Answer [8]

提示

约束

• $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 \ne y$。
• 通过若干条航线相连，可以从任意一个机场到达任意另一个机场。
• 对每个机场，连接它与其他机场的航线数量至多为 $3$。

子任务

1.（$15$ 分）$Q = 1$。
2.（$85$ 分）$Q \ge 2$。

子任务 1 的评分

若你的程序在子任务 $1$ 的任意场景中被判为 Wrong Answer，则该子任务得分为 $0$。

若你的程序正确回答子任务 $1$ 的所有测试用例，得分按下述规则计算。设 $L_1$ 为 Ali 发给 Benjamin 的字符串的最大长度。

$L_1$ 的取值	得分
$150\,001 \le L_1 \le 300\,000$	$7$ 分
$20\,001 \le L_1 \le 150\,000$	$11$ 分
$L_1 \le 20\,000$	$15$ 分

子任务 2 的评分

若你的程序在子任务 $2$ 的任意场景中被判为 Wrong Answer，则该子任务得分为 $0$。

若你的程序正确回答子任务 $2$ 的所有测试用例，得分按下述规则计算。设 $L_2$ 为 Ali 发给 Benjamin 的字符串的最大长度。注意：若 $1\,401 \le L_2$，该子任务得分为 $0$。

$L_2$ 的取值	得分
$1\,401 \le L_2 \le 300\,000$	$0$ 分
$71 \le L_2 \le 1\,400$	$52 - 35 \times \log_{10}\!\bigl(\frac{L_2}{70}\bigr)$ 分（向下取整）
$45 \le L_2 \le 70$	$87 - 0.5 \times L_2$ 分（向下取整）
$25 \le L_2 \le 44$	$109 - L_2$ 分
$L_2 \le 24$	$85$ 分

样例交互

以下为样例评测器的样例输入与对应的函数调用。在该示例中，Ali 在 Init 中为机场 $0, 1, 2, 3$ 设置的 ID 码分别为 $12, 21, 25, 27$。

样例输入 1

Ali 的调用	Ali 的返回值	Benjamin 的调用	Benjamin 的返回值
$\texttt{Init(4,[0,1,2],[1,2,3])}$
$\texttt{SetID(0,12)}$
$\texttt{SetID(1,21)}$
$\texttt{SetID(2,25)}$
$\texttt{SetID(3,27)}$
		$\texttt{SendB(12,25)}$	$\texttt{"0000011111000011111"}$
$\texttt{SendA("00...11")}$	$\texttt{"10"}$
		$\texttt{Answer("10")}$	$\texttt{2}$

在该样例中，有 $N (= 4)$ 个机场与三条航线：

• 一条连接机场 $0$ 与机场 $1$ 的航线；
• 一条连接机场 $1$ 与机场 $2$ 的航线；
• 一条连接机场 $2$ 与机场 $3$ 的航线。

从机场 $x (= 0)$ 到机场 $y (= 2)$ 至少需要乘坐 $2$ 条航线，因此 Answer 应返回 $2$。

注意：SendB 的返回值并不是机场编号 $(x, y) = (0, 2)$，而是机场的 ID 码 $(X, Y) = (12, 25)$。

样例输入 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

在该样例中，$Q = 2$ 个场景：

• 对于第一个场景，Answer 应返回 $9$。
• 对于第二个场景，Answer 应返回 $6$。