This is a communication problem.

The territory of country P can be viewed as an undirected connected graph with $N$ vertices and $N-1$ edges, where the $i$-th edge ($0 \leq i \leq N-2$) connects vertices $A_i$ and $B_i$. The vertices are numbered with positive integers from $1$ to $N$.

The Pre-SDOI Training Camp (also known as "Public Easy Round #2") is about to be held in country P. As a foreign candidate, you want to know the location of the exam in advance and hope to sneak into the exam site before the information is officially released. To obtain this information, you have contacted an insider from country P who has learned through an intelligence network that the exam location has been set at vertex $T$. Since the road information and the exam location are classified, the insider cannot send this information to you directly. Instead, they decide to place a sign on each vertex $i$ ($1 \leq i \leq N$) marked with a non-negative integer $X_i$.

Subsequently, you can arrive at a vertex $S$ in country P by taking transportation. However, since neither you nor the insider knows the transportation information in advance, the insider cannot know the value of $S$ until you actually arrive. When you are at a vertex, you can obtain the following information:

• The index of your current vertex $S$
• The number $F$ marked on your current vertex
• The number of vertices $L$ adjacent to your current vertex
• The indices of the vertices adjacent to your current vertex $P_0, P_1, \dots, P_{L-1}$
• The numbers $Q_0, Q_1, \dots, Q_{L-1}$ marked on the vertices adjacent to your current vertex

You want to use this information to determine whether you have reached vertex $T$. If not, you must determine which vertex to move to next, such that the vertex lies exactly on the unique simple path between $S$ and $T$.

To avoid the insider being discovered, both parties want to develop a strategy that minimizes the numbers marked by the insider.

Implementation Details

This is a communication problem; only the C++ language is supported.

You need to submit two programs, Spy and Participant, to implement the strategies for both parties.

Spy

You need to submit a program named Spy.cpp to describe the process of the insider passing information.

You must include the header file Spy.h and implement the following function:

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

• In each test case, this function will be called exactly once.
• N represents the number of vertices $N$ in country P.
• T represents the vertex index $T$ where the competition is held.
• A is an array of length $N-1$: $A_0, A_1, \dots, A_{N-2}$.
• B is an array of length $N-1$: $B_0, B_1, \dots, B_{N-2}$.
• This function must return an array of length exactly $N$: $X_0, X_1, \dots, X_{N-1}$, where $X_i$ describes the number assigned by the insider to vertex $i+1$.
  • You must ensure $X_i \geq 0$.

Participant

You need to submit a program named Participant.cpp to describe your strategy.

You must include the header file Participant.h and implement the following function:

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

• In each test case, this function will be called exactly once.
• S represents the index of the vertex where you are currently located.
• F represents the number $F$ on vertex $S$.
• L represents the degree $L$ of vertex $S$.
• P is an array of length $L$: $P_0, P_1, \dots, P_{L-1}$, representing all neighbors of $S$.
• Q is an array of length $L$: $Q_0, Q_1, \dots, Q_{L-1}$, where the $i$-th number ($0 \leq i \leq L-1$) represents the number marked on vertex $P_i$.

This function must return the answer, specifically:

• If vertex $S$ is the competition location (i.e., $S = T$), return $S$.
• Otherwise, return a vertex index $x \in \{ P_0, P_1, \dots, P_{L-1} \}$, indicating that you should move from the current vertex to vertex $x$.
  • It is easy to see that such a vertex $x$ is unique.

Examples

The provided files include a sample grader grader.cpp, which can help you understand the problem and test your program. During the final evaluation, the grader used will be different from this sample grader; your program should not rely on the implementation of the sample grader.

You can compile the executable answer using the following command:

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

The executable answer will read input data from standard input in the following format:

• The first line contains three integers $N, S, T$.
• The next $N-1$ lines each contain two integers $A_i, B_i$.

The executable will output the following information to standard output:

• The first line contains an integer $Y$, representing the return value of the Participant function.
• The second line contains an integer $m$, representing the maximum value among all elements in the array returned by the Spy function.

Please note that the sample grader does not perform any checks on the correctness of your program; it does not check if you share global variables, nor does it check if the value returned by your program is correct.

Examples 1

Input 1

5 3 2
1 3
3 2
3 4
4 5

Output 1

2
3

Note

One possible communication process: 1. Grader calls Spy(...). 2. Spy returns $\{0, 1, 1, 3, 1\}$. 3. Grader calls Participant(...). 4. Participant returns $2$.

Constraints

For all data, $2 \leq N \leq 10^5$, $1 \leq S, T \leq N$, $1 \leq A_i, B_i \leq N$, and the given graph is guaranteed to be connected.

In each test case, if your program exceeds the time limit, exceeds the memory limit, encounters a runtime error, or the final output value $Y$ is incorrect, you will receive $0$ points.

Otherwise, your score depends on the value of $m$: