Problem Statement

There is a tree with $N$ vertices numbered from $1$ to $N$. The $i$-th edge connects vertices $A_i$ and $B_i$. Here, $N$ is even, and furthermore, this tree has a perfect matching. Specifically, for each $i$ ($1 \leq i \leq N/2$), it is guaranteed that $A_i=i \times 2-1$ and $B_i=i \times 2$.

You will perform the following operation $N/2$ times:

• Choose two leaves (vertices with degree exactly $1$) and remove them from the tree. Here, the tree after removal must still have a perfect matching. In this problem, we consider a graph with zero vertices to be a tree as well.

For each operation, its score is defined as the distance between the two chosen vertices (the number of edges on the simple path connecting the two vertices).

Show one procedure that maximizes the total score. It can be proved that there always exists a procedure to complete $N/2$ operations under the constraints of this problem.

Constraints

• $2 \leq N \leq 250000$
• $N$ is even.
• $1 \leq A_i < B_i \leq N$ ($1 \leq i \leq N-1$)
• $A_i=i \times 2 -1$, $B_i=i \times 2$ ($1 \leq i \leq N/2$)
• The given graph is a tree.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Print a solution in the following format:

X_1 Y_1
X_2 Y_2
\vdots
X_{N/2} Y_{N/2}

Here, $X_i$ and $Y_i$ are the two vertices chosen in the $i$-th operation. If there are multiple solutions, you may print any of them.