Problem Description

There is a tree consisting of $ N $ vertices numbered from $ 1 $ to $ N $. The $ i $-th edge connects vertex $ A_i $ and vertex $ B_i $. Here, $ N $ is even, and 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:

• Select two leaf vertices (vertices with exactly one edge) and remove them from the tree. However, the tree after removal must still have a perfect matching. Note that in this problem, a tree with $ 0 $ vertices is also considered a tree.

The score for each operation is defined as the distance between the two selected vertices (the number of edges on the simple path connecting these two vertices).

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

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer 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 selected in the $ i $-th operation. If multiple solutions exist, any one of them can be output.

Sample Input and Output

Sample Input #1

4
1 2
3 4
2 3

Sample Output #1

4 1
2 3

Sample Input #2

8
1 2
3 4
5 6
7 8
2 3
1 5
1 7

Sample Output #2

4 8
7 6
5 3
2 1

Sample Input #3

14
1 2
3 4
5 6
7 8
9 10
11 12
13 14
2 8
4 11
5 12
7 13
11 14
9 13

Sample Output #3

1 6
5 2
8 12
3 7
10 4
11 9
13 14

Sample Input #4

20
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
8 10
16 18
16 19
5 9
10 17
2 13
7 14
3 7
3 12

Sample Output #4

6 1
2 15
20 13
14 19
16 4
11 18
17 12
3 5
9 7
8 10

Notes/Hints

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

Sample Explanation 1

The procedure for the sample output is as follows:
- First operation: Remove vertices $ 4 $ and $ 1 $. The remaining tree consists of vertices $ 2 $ and $ 3 $ and has a perfect matching. The score of this operation is $ 3 $.
- Second operation: Remove vertices $ 2 $ and $ 3 $. The remaining tree has $ 0 $ vertices and has a perfect matching. The score of this operation is $ 1 $.
- The total score is $ 3 + 1 = 4 $. It is not possible to achieve a total score greater than $ 4 $, so this sample input can be correctly answered with this output.

见题面 Input 部分

见题面 Output 部分