这是一道通信题

P 国的国土可被视为一张 $N$ 个点 $N-1$ 条边的无向连通图，其中第 $i$ ($0 \leq i \leq N-2$) 条边连接了顶点 $A_i$ 与 $B_i$。顶点的编号均为 $1 \sim N$ 中的正整数。

Pre-SDOI Training Camp（也被称作 Public Easy Round #2） 即将在 P 国举办，作为一名外国考生，你想要提前得知考试的地点，并希望在考试情报公布前潜入考试地点。为了提前得知考试情报，你已经联系了来自 P 国的一名内鬼，他通过情报网络得知了考试的举办地点已被安排在了顶点 $T$。由于 P 国的道路信息与考试地点属于机密信息，他无法将这些情报发送给你，于是他决定在每个顶点 $i$ ($1 \leq i \leq N$) 上放置一个告示牌，并在上面标记一个非负整数 $X_i$。

随后，你可以通过搭乘 P 国的交通工具到达 P 国的一个顶点 $S$，但是由于你与内鬼事先都不了解 P 国的交通信息，因此在你真正到达前，内鬼无法得知 $S$ 的值。当你位于一个点时，你可以得到以下信息：

• 你当前所在的顶点的编号 $S$
• 你当前所在的顶点上所标记的数字 $F$
• 与你当前所在的顶点相邻的顶点数量 $L$
• 与你当前所在的顶点相邻的顶点的编号 $P_0,P_1, \cdots, P_{L-1}$
• 与你当前所在的顶点相邻的顶点上所标记的数字 $Q_0,Q_1, \cdots, Q_{L-1}$

你想要通过这些信息，得知你是否已经到达顶点 $T$。如果没有，那么你下一步应该前往哪一个顶点，使得该顶点恰好在 $S$ 与 $T$ 所构成的唯一简单路径上。

为了避免内鬼被发现，你们双方想要制定一个策略，使得内鬼所标记的数字尽可能小。

实现细节

这是一道通信题，本题仅支持 C++ 语言。

你需要提交两个程序，分别为 Spy 与 Participant，来实现你们双方的策略。

Spy

你需要提交的程序名为 Spy.cpp，描述内鬼传递信息的过程。

你需要包含头文件 Spy.h，并实现以下函数：

std::vector <int> Init(int N, int T, std::vector <int> A, std::vector <int> B)

• 在每个测试点中，该函数会被调用恰好一次。
• $\texttt{N}$ 表示 P 国的顶点数量 $N$。
• $\texttt{T}$ 表示比赛举办地点的顶点编号 $T$。
• $\texttt{A}$ 是一个长度为 $N-1$ 的数组 $A_0, A_1, \cdots, A_{N-2}$。
• $\texttt{B}$ 是一个长度为 $N-1$ 的数组 $B_0, B_1, \cdots, B_{N-2}$。
• 该函数需要返回一个长度恰好为 $N$ 的数组 $X_0,X_1,\cdots,X_{N-1}$，其中 $X_i$ 描述内鬼给点 $i+1$ 赋予的数字。
  • 你需要保证 $X_i \geq 0$。

Participant

你需要提交的程序名为 Participant.cpp，描述你的策略。

你需要包含头文件 Participant.h，并实现以下函数：

int Query(int S, int F, int L, std::vector <int> P, std::vector <int> Q)

• 在每个测试点中，该函数会被调用恰好一次。
• $\texttt{S}$ 表示你此时所在的顶点编号 $S$。
• $\texttt{F}$ 表示顶点 $S$ 上的数字 $F$。
• $\texttt{L}$ 表示顶点 $S$ 的度数 $L$。
• $\texttt{P}$ 是一个长度为 $N-1$ 的数组 $P_0, P_1, \cdots, P_{L-1}$，表示 $S$ 的所有邻居。
• $\texttt{Q}$ 是一个长度为 $N-1$ 的数组 $Q_0, Q_1, \cdots, Q_{L-1}$，其中第 $i$ ($0 \leq i \leq L-1$) 个数表示顶点 $P_i$ 上的数字。

该函数需要返回答案，具体地：

• 如果顶点 $S$ 即为比赛举办地点（即 $S = T$），则需要返回 $S$。
• 否则，返回一个顶点编号 $x \in \{ P_0,P_1,\cdots,P_{L-1} \}$，表示应从当前顶点前往顶点 $x$。
  • 容易发现，这样的顶点 $x$ 是唯一的。

样例交互库

下发文件中包含了样例交互库 grader.cpp，该交互库可以帮助你理解这道题目的题意并测试你的程序。在最终评测时，所使用的交互库与该样例交互库有所不同，你的程序不应依赖该样例交互库的实现。

你可以使用以下命令编译出可执行文件 answer

g++ grader.cpp Spy.cpp Participant.cpp -o answer -O2

可执行文件 answer 将从标准输入中读入以下格式的输入数据：

• 输入的第一行包含三个整数 $N,S,T$。
• 接下来 $N-1$ 行，每行两个整数 $A_i, B_i$。

可执行文件将向标准输出中输出以下信息：

• 输出的第一行包含一个整数 $Y$，表示函数 Participant 的返回值。
• 输出的第二行包含一个整数 $m$，表示函数 Spy 所返回的数组中所有元素的最大值。

请注意，样例交互库不会对你的程序的正确性做任何检查，即样例交互库不会检查你是否共用了全局变量，也不会检查你的程序所返回的值是否正确。

样例 1

考虑以下对样例交互库的输入数据：

5 3 2
1 3
3 2
3 4
4 5

以下是一种可能的通信过程：

可执行文件向标准输出中输出

2
3

子任务

对于所有数据，$2 \leq N \leq 10^5$，$1 \leq S,T \leq N$，$1 \leq A_i, B_i \leq N$，保证给定的图联通。

在每个测试点中，如果你的程序超出了时间限制、超出了空间限制、发生了运行时错误，或最终输出的 $Y$ 的值不正确，则你获得 $0$ 分。

否则，设该测试点的满分为 $W$，你的得分与 $m$ 的值有关：

• 若 $0 \leq m \leq 1$，则你的得分为 $W$。
• 若 $2 \leq m \leq 4$，则你的得分为 $\dfrac{W}{\alpha^m}$。
• 若 $5 \leq m \leq 10$，则你的得分为 $\dfrac{W}{\beta^m}$。
• 若 $10 < m \leq 10^5$，则你的得分为 $\dfrac{W}{\beta^{25}}$。
• 否则，你的得分为 $0$。
• 其中 $\alpha = \frac{3}{2}, \beta = \frac{7}{4}$

本题中 $W=100$，你可以通过该得点分布表来参考不同的 $m$ 所对应的得点。