This is an interactive problem.

Description

Little M is playing a Real Time Strategy (RTS) game. Unlike most similar games, the map of this game is a tree. That is, the map can be represented as a connected graph consisting of $n$ nodes and $n-1$ edges. These nodes are numbered $1 \sim n$.

Each node has two possible states: "known" or "unknown". At the beginning of the game, only node $1$ is known. During the game, Little M can attempt to explore more nodes. Specifically, in each operation, Little M needs to choose a known node $x$ and an arbitrary node $y$ different from $x$ (node $y$ can be unknown). Then, the game's automatic pathfinding system will provide the second node $z$ on the shortest path from $x$ to $y$, which is the node adjacent to $x$ on the shortest path from $x$ to $y$. At this point, if node $z$ is unknown, Little M will mark it as known.

The goal of this game is to make all nodes known using at most $T$ exploration operations. However, Little M is still a novice at this game, and she hopes to get your help.

To make the game process easier, Little M has provided you with an interactive library, details of which can be found in the Task Introduction and Implementation Details sections.

Additionally, Little M has provided some hints for the game, which can be found in the final section of the problem, Note.

Task Introduction

You need to implement a function play to help Little M achieve the game's goal.

• play(n, T, dataType)
• $n$ is the number of nodes in the tree;
• $T$ is the limit on the number of exploration operations;
• $dataType$ is the data type of the test case; see Constraints for details.

In each test case, the interactive library will call the play function exactly once. Before this function is called, the game is in its initial state.

You can call the function explore to help you explore more nodes in the game, but the number of calls to this function cannot exceed $T$.

• explore(x, y)
• $x$ is a known node;
• $y$ is an arbitrary node different from $x$ (it does not have to be a known node);
• This function returns the index of the second node on the shortest path from node $x$ to $y$.

After the play function returns, the interactive library will check the state of the game: the game's goal is considered complete only if every node is known.

Implementation Details

You must submit exactly one source file rts.cpp/c/pas to implement the above function, following the naming and interface conventions below.

For C/C++ contestants: Your source code must include the header file rts.h. You need to implement the function play: void play(int n, int T, int dataType); The interface for the function explore is as follows: int explore(int x, int y);

For Pascal contestants: You need to use the unit graderhelperlib. You need to implement the function play: procedure play(n, T, dataType : longint); The interface for the function explore is as follows: function explore(x, y : longint) : longint;

Testing Your Program

For C/C++ contestants: You need to compile your program in the problem directory using the following commands: For C: gcc grader.c rts.c -o rts -O2 -lm For C++: g++ grader.cpp rts.cpp -o rts -O2 -lm

For Pascal contestants: You need to compile your program in the problem directory using the following command: fpc grader.pas -o"rts" -O2

The executable will read data from standard input in the following format: The first line contains three integers $n, T, dataType$, where $n \in [2, 3 \times 10^5]$, $T \in [1, 5 \times 10^6]$, and $dataType \in [1, 3]$. The next $n-1$ lines each contain two integers $u, v$, where $1 \le u, v \le n$ and $u \neq v$, representing an edge between $u$ and $v$. Your input must guarantee that these $n-1$ edges form a tree.

After reading the input, the interactive library will call the play function. If you call explore more than $T$ times, the interactive library will output a detailed error message and exit. Next, the interactive library will determine if the game goal is achieved. If it is, it will output "Correct", otherwise it will output the corresponding error message.

If the parameters passed to the explore function are invalid (e.g., $x, y$ are not in the range $1$ to $n$, or $x$ is not a known node, or $x$ equals $y$), the interactive library will output a detailed error message and exit.

If you want to use your own input files for testing, please ensure the input file conforms to the format requirements above; otherwise, the program's correct execution is not guaranteed.

Examples

Input 1

4 100 1
1 3
3 4
3 2

Output 1

Correct

Note 1

This is the output obtained using the grader and the correct source program from the problem directory. For this example, one possible sequence of calls to the explore function is: explore(1, 2), returns 3 explore(3, 2), returns 2 explore(2, 4), returns 3 explore(3, 4), returns 4

Examples 2 & 3

See rts/rts2.in and rts/rts2.ans (Example 2) or rts/rts3.in and rts/rts3.ans (Example 3) in the contestant directory.

Subtasks

There are 20 test cases, each worth 5 points. For all test cases, $2 \le n \le 3 \times 10^5$, $1 \le T \le 5 \times 10^6$, and $1 \le dataType \le 3$. The different $dataType$ values correspond to the following data types: For $dataType = 1$, there are no special restrictions. For $dataType = 2$, the game map is a complete binary tree rooted at node 1. That is, there exists a permutation $a$ of $1 \sim n$ such that $a_1 = 1$, and node $a_i$ ($1 < i \le n$) is connected to node $a_{\lfloor i/2 \rfloor}$. * For $dataType = 3$, the game map is a chain. That is, there exists a permutation $a$ of $1 \sim n$ such that node $a_i$ ($1 < i \le n$) is connected to node $a_{i-1}$.

The values of $n, T, dataType$ for each test case are as follows:

Note

Here are some helpful hints from Little M: A graph (undirected graph) consists of nodes and edges. Edges are unordered pairs of nodes used to describe the relationships between nodes. A path is a non-empty sequence of nodes such that every two adjacent nodes in the sequence are connected by an edge. Two nodes are connected if and only if there exists a path starting at one node and ending at the other. A graph is connected if and only if every pair of nodes in the graph is connected. A tree with $n$ nodes is a connected graph consisting of $n$ nodes and $n-1$ edges. The shortest path between two nodes is the path with the minimum sequence length among all possible paths connecting the two nodes. In a tree, the shortest path connecting any two nodes is unique. Attempting to gain points by accessing input/output files, attacking the judging system, or attacking the interactive library is considered cheating, and any points obtained will be invalid.