这是一道通信题。

JOI 共和国中有 $N$ 座机场，编号为 $0,1,\dots ,N-1$。其中有 $N-1$ 条航线，编号为 $0,1,\dots ,N-2$。

航线 $i$ $(0\le i\le N-2)$ 双向连接机场 $U_i$ 和 $V_i$。保证从每座机场都能经过若干条航线到达任意其他机场。

Benjamin 准备在 JOI 共和国进行一次说走就走的旅行。

他从游乐园所在的机场出发，且想在旅行的最后一天到达温泉所在的机场。游乐园在机场 $x$，而温泉在机场 $y$。

然而 Benjamin 不知道任何航线的信息，所以他会和航空公司的一位工作人员 Ali 联系。Benjamin 想知道他从机场 $x$ 到机场 $y$ 所需要经过的航线条数的最小值。Ali 知道所有航线的信息，但弱小可怜又无助的 Benjamin 并不知道应该怎么规划路线。

1. Ali 为每座机场设置了一个识别码。识别码是一个 $[0,2N+19]$ 内的整数。
2. Benjamin 知道机场 $x$ 的识别码 $X$ 和机场 $y$ 的识别码 $Y$。
3. Benjamin 向 Ali 发送了一封电子邮件。这封邮件是一个长度恰为 $20$ 的字符串，且仅由 $\mathtt{\text{0}},\mathtt{\text{1}}$ 构成。
4. Ali 给 Benjamin 写一封信。这封信包含一个长度为 $[1,300000]$ 中的整数的字符串，且仅由 $\mathtt{\text{0}},\mathtt{\text{1}}$ 构成。

请写两个程序，分别实现工作人员 Ali 和旅行者 Benjamin 的策略。

注意，在第 $2$ 步中，Benjamin 得知识别码 $X,Y$ 但没有得知机场编号 $x,y$。

任务

本题仅支持符合 C++11 及以上标准的 C++ 语言。

你需要提交两份文件，分别为 Ali.cpp 和 Benjamin.cpp。

Ali

第一份文件是 Ali.cpp。其中应该实现 Ali 的策略，即包含以下两个函数。且其应当使用预编译指令 #include 包含 Ali.h。

void Init(int N, std::vector<int> U, std::vector<int> V);

这个函数实现了 Ali 设置识别码的过程。对于每组测试用例，这个函数将恰被调用一次。

• 参数 $\mathtt{\text{N}}$ 是 JOI 共和国的机场个数。
• 参数 $\mathtt{\text{U}},\mathtt{\text{V}}$ 是长度为 $N-1$ 的数组。表示 $\mathtt{\text{U[i]}},\mathtt{\text{V[i]}}$ 是第 $i$ 条航线连接的机场编号 $U_i,V_i$ $(0\le i\le N-2)$。

std::string SendA(std::string S);

这个函数实现了 Ali 给 Benjamin 写信的过程。对于每组测试用例，这个函数将恰在调用 SendB（见下）后被调用一次。

• 参数 $\mathtt{\text{S}}$ 是一个长度为 $20$ 的字符串，表示 Benjamin 发给 Ali 的邮件。
• 该函数返回一个长度为 $[1,300000]$ 中的整数的字符串，表示 Ali 写给 Benjamin 的信。否则你的答案会被判定为 Wrong Answer [5]。
• 返回值的每个字符都是 $\mathtt{\text{0}}$ 或 $\mathtt{\text{1}}$。否则你的答案会被判定为 Wrong Answer [6]。

在每次对 Init 的调用中，你需要每座机场调用如下函数。总共调用 $N$ 次。

void SetID(int p, int value);

• 参数 $\mathtt{\text{p}}$ 表示 Ali 正在设置机场 $\mathtt{\text{p}}$ 的识别码。满足 $0\le \mathtt{\text{p}}\le N-1$。否则你的答案会被判定为 Wrong Answer [1]。
• 参数 $\mathtt{\text{value}}$ 表示 Ali 选定的识别码。满足 $0\le \mathtt{\text{value}}\le 2N+19$。否则你的答案会被判定为 Wrong Answer [2]。
• 不允许对于同一个 $\mathtt{\text{p}}$ 调用多于一次 SetID。否则你的答案会被判定为 Wrong Answer [3]。
• 当 Init 函数调用结束时，SetID 的调用次数应当恰为 $N$。否则你的答案会被判定为 Wrong Answer [4]。

当对 SetID 的调用被判作 Wrong Answer 时，你的程序会立即被结束。

Benjamin

第二份文件是 Benjamin.cpp。其中应该实现 Benjamin 的策略，即包含以下两个函数。且其应当使用预编译指令 #include 包含 Benjamin.h。

std::string SendB(int N, int X, int Y);

这个函数实现了 Benjamin 给 Ali 发电子邮件的过程。对于每组测试用例，这个函数将恰在调用 Init 后被调用一次。

• 参数 $\mathtt{\text{N}}$ 是 JOI 共和国的机场个数。
• 参数 $\mathtt{\text{X}}$ 是机场 $x$ 的识别码。
• 参数 $\mathtt{\text{Y}}$ 是机场 $y$ 的识别码。
• 该函数返回一个长度为 $20$ 的字符串，表示 Benjamin 发给 Ali 的邮件。否则你的答案会被判定为 Wrong Answer [7]。
• 返回值的每个字符都是 $\mathtt{\text{0}}$ 或 $\mathtt{\text{1}}$。否则你的答案会被判定为 Wrong Answer [8]。

int Answer(std::string T);

这个函数应当计算出 Benjamin 从机场 $x$ 到机场 $y$ 所需要经过的航线条数的最小值。对于每组测试用例，这个函数将恰在调用 SendA 后被调用一次。

• 参数 $\mathtt{\text{T}}$ 是一个长度为 $[1,300000]$ 中的整数的字符串，表示 Ali 写给 Benjamin 的信。
• 这个函数应当返回从机场 $x$ 到机场 $y$ 所需要经过的航线条数的最小值。

提示

• 你的程序可以实现其他函数以供内部使用，或者使用全局变量。提交的文件会和评分器一同编译，得到单独一个可执行文件。所有全局变量和内部函数应当在一个未使用过的命名空间内声明，以免与其他程序冲突。评测时，Ali 和 Benjamin 的策略会分为两个进程，无法共享全局变量。
• 你的程序不得使用标准输入输出流，也不得以任何方式访问任何文件。然而，你可以输出调试信息到标准错误流。

评分方式

一组测试数据包含 $Q$ 个测试用例，编号为 $0,1,\dots ,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。
3. 调用函数 SendB。
4. 调用函数 SendA。
5. 调用函数 Answer。

当你的程序被判作 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

若编译成功，将会生成一个可执行文件 $\mathtt{\text{grader}}$。

请注意，实际使用的评分器与下发的样例评分器不同。样例评分器仅会有单个进程，从标准输入中读取输入数据并将结果输出到标准输出。

样例评分器输入格式

第一行，一个正整数 $Q$，表示这个测试数据包含 $Q$ 组测试用例。

对于每组测试用例：

第一行，三个整数 $N,x,y$，分别表示机场个数，游乐园与温泉所在的机场编号。

接下来 $N-1$ 行，其中第 $i+1$ $(0\le i\le N-1)$ 行包含两个正整数 $U_i,V_i$，表示航线 $i$ 连接的机场编号。

样例评分器输出格式

如果你的程序被判定为 Wrong Answer [1-8]，样例评分器将以 “$\mathtt{\text{Wrong Answer [1]}}$” 的格式输出（不包含引号）。

否则，对于每组测试用例，其输出函数 $\mathtt{\text{Answer}}$ 的返回值和 Ali 给 Benjamin 写的信的最大长度。样例评分器并不检查 $\mathtt{\text{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，那么即使你的程序在之后的测试用例中被判为 Wrong Answer [1-8]，样例评分器也会按如下方式输出中间的结果。

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

样例一

input

1
4 0 2
0 1
1 2
2 3

explanation

这里有样例评分器的一个样例输入和对应的函数调用。其中，机场 $0,1,2,3$ 的识别码分别为 $12,21,25,27$。

在样例输入中，有 $N(=4)$ 座机场和 $3$ 条航线。

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

由于 Benjamin 需要经过至少 $2$ 条航线才能从机场 $x(=0)$ 到机场 $y(=2)$，所以函数 Answer 应当返回 $2$。

注意函数 SendB 的参数不是机场编号 $(x,y)=(0,2)$，而是识别码 $(X,Y)=(12,25)$。

样例二

input

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

explanation

在这组数据中，有 $Q=2$ 组测试用例。

• 对于第一组用例，$\mathtt{\text{Answer}}$ 应当返回 $9$。
• 对于第二组用例，$\mathtt{\text{Answer}}$ 应当返回 $6$。

数据范围

对于所有数据，满足：

• $1\le Q\le 50$。
• $2\le N\le 10000$。
• $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 评分方式

如果你的程序在子任务 1 的任何用例中被判为 Wrong Answer，则你在该子任务的分数为 $0$。

如果你的程序正确回答了子任务 1 中的所有用例，你的分数将按如下方式计算。其中 $L_1$ 是 Ali 给 Benjamin 写的信的最大长度。

子任务 2 评分方式

如果你的程序在子任务 2 的任何用例中被判为 Wrong Answer，则你在该子任务的分数为 $0$。

如果你的程序正确回答了子任务 2 中的所有用例，你的分数将按如下方式计算。其中 $L_2$ 是 Ali 给 Benjamin 写的信的最大长度。注意，若 $L_2\ge 1401$，你在该子任务的分数即为 $0$。

保证合法的交互过程中，评测库不会使用超过共 $\mathtt{\text{1s}}$ 时间，分别不会使用超过 $\mathtt{\text{32MB}}$ 空间。

时间限制：两份程序共 $\mathtt{\text{4s}}$

空间限制：两份程序分别 $\mathtt{\text{512MB}}$