This is an interactive problem.

After a rebellion, the upper government has appointed you as the mayor of the city to oversee its reconstruction. You need to build $N$ passages in the city.

This is a large city with $2N$ districts, numbered $1, 2, \dots, 2N$, connected by $2N-1$ bidirectional roads. In other words, the districts and roads of the city form a tree.

All passages are one-way. You need to select exactly $N$ districts as entrances and the remaining $N$ districts as exits. The $N$ passages must cover all entrances and exits without overlap. Furthermore, to avoid scrutiny from the upper government regarding your construction plan, there must not exist two passages $(a, b)$ and $(c, d)$, where $a, c$ are entrances and $b, d$ are exits, such that $\operatorname{dis}(a, b) < \operatorname{dis}(a, d) < \operatorname{dis}(c, d)$. Here, $\operatorname{dis}(x, y)$ is defined as the distance between district $x$ and district $y$, i.e., the minimum number of roads to traverse.

However, the rebels burned many documents, leaving you with only an old city map. The current city has undergone many expansions since the time depicted in your map. Your map only contains the current city's districts $1 \dots N$ and the $N-1$ roads that connected them at that time. The expansion did not destroy the city's layout: for any two roads $(a, b)$ and $(b, c)$ that shared exactly one district before the expansion, the shortest path from $a$ to $b$ and the shortest path from $b$ to $c$ after the expansion still share exactly one district, $b$.

Due to a shortage of personnel, you can only collect information through the following two channels:

1. Given a set of districts $A$ and a set of districts $B$ (where $|B| > 1$), for each district $x \in A$, you can determine whether the district in $B$ that is farthest from $x$ along all paths $(x, y)$ ($y \in B$) (i.e., the $\operatorname{LCA}$ of the districts in $B$ when $x$ is the root) is a given point $P$.
2. Given two districts $x, y$, you can determine $\operatorname{dis}(x, y)$.

Please complete the task of building the passages.

Implementation Details

You do not need to, and should not, implement the main function.

You must include the header file passageconstruction.h.

You must implement the following function:

std::vector<std::pair<int,int>> ConstructPassages(int N, const std::vector<std::pair<int,int>> &E);

$N$ is as described in the problem, and $E$ represents the roads on your map. You need to return exactly $N$ pairs, representing a valid construction plan. Each pair represents a passage, where first is the entrance and second is the exit. Specifically, if no solution exists, return an empty vector.

Available functions:

std::vector<int> QueryLCA(const std::vector<int> &A, const std::vector<int> &B, int P);

This function represents operation 1, with $A, B, P$ as described above. It is guaranteed that the returned vector has the same size as A.size() and contains only $0$ and $1$. The $k$-th item (starting from $0$) is $1$ if and only if the $\operatorname{LCA}$ of the districts in $B$ when $A_k$ is the root is $P$.

int GetDistance(int x,int y);

Queries the distance, with $x, y$ as described above.

int getSubtaskID();

Retrieves the subtask ID. In the sample grader, this function always returns $0$.

It is guaranteed that the city is fixed at the start of the interaction; the grader is not adaptive.

Examples

The files sample_grader.cpp and passageconstruction.h are provided. You can generate the executable using the command g++ sample_grader.cpp <your source file> -o passageconstruction -O2 -std=c++14.

Note that the grader used for evaluation is different from the sample grader.

Input

The first line contains an integer $N$, as described in the problem.

The next $2N-1$ lines each contain two integers, representing a road in the city. Note that $1, 2, \dots, N$ must satisfy the conditions mentioned above.

Note that the sample grader does not check if the input file is valid; behavior is undefined if the input is invalid.

Output

The grader returns $0$ if the program terminates normally and the answer is correct, and $1$ if the answer is incorrect or an interaction error occurs.

Error messages for incorrect answers or interaction errors:

• Index out of range: District number is not an integer in $[1, 2N]$.
• Invalid construction plan: The format of the returned plan is incorrect.
• Condition not satisfied: The returned plan does not satisfy the conditions mentioned above.
• Invalid type 1 query: The condition $|B| > 1$ was not met during operation 1.

Messages for correct answers:

• Accepted with a+b operations, sum of size(s)=c+d. Here $a, b$ are the number of operations 1 and 2, respectively, and $c = \sum |A|, d = \sum |B|$.

Message if no solution is reported:

• Reported no solution with a+b operations, sum of size(s)=c+d. $a, b, c, d$ are as defined above.

Constraints

Let $C_1$ be the number of operation 1 calls, $C_2$ be the number of operation 2 calls, $S_1 = \sum |A|$, and $S_2 = \sum |B|$.

Special Property A: Each district in the city is connected to at most two roads.

Special Property B: Each district in the city is connected to at most three roads.

Special Property C: It is guaranteed that all roads on your map still exist.

Scoring: Within a subtask, if $C_1, C_2, S_1, S_2$ are all $\le$ the corresponding limits, the subtask receives full marks.

Otherwise, let the limits be $C_1^{Lim}, C_2^{Lim}, S_1^{Lim}, S_2^{Lim}$, and let $v = \max\left(\frac{C_1}{C_1^{Lim}}, \frac{C_2}{C_2^{Lim}}, \frac{S_1}{S_1^{Lim}}, \frac{S_2}{S_2^{Lim}}\right)$. If $v > 2$, the subtask receives $0$ points; otherwise, the score for the subtask is the full score $\times (1.4 - 0.5v)^2$.

The grader is guaranteed to run within $0.1\text{s}$ and use $\le 64\text{MiB}$ of memory for the given data range. The time limit for subtasks $1 \sim 7$ is $1\text{s}$, and the time limit for the remaining subtasks is $2.4\text{s}$.