题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。这里 $N$ 是偶数，并且这棵树存在一个完全匹配。具体来说，对于每个 $i$（$1 \leq i \leq N/2$），都有 $A_i = i \times 2 - 1, B_i = i \times 2$。

你需要进行如下操作共 $N/2$ 次：

• 每次选择两个叶子（度数恰好为 $1$ 的顶点），并将它们从树中删除。此时，删除后的树也必须仍然存在完全匹配。注意，在本题中，顶点数为 $0$ 的情况也视为一棵树。

对于每次操作，其得分定义为“所选的两个顶点之间的距离（即连接这两个顶点的简单路径上的边数）”。

请给出一种操作顺序，使得总得分最大。可以证明，在本题的约束下，总能完成 $N/2$ 次操作。

输入格式

输入从标准输入读入，格式如下：

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

输出格式

请按如下格式输出答案：

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

其中，$X_i, Y_i$ 表示第 $i$ 次操作中选择的两个顶点。如果有多种方案，输出任意一种均可。

样例 1

输入

4
1 2
3 4
2 3

输出

4 1
2 3

样例 2

输入

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

输出

4 8
7 6
5 3
2 1

样例 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

输出

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

样例 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

输出

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

说明/提示

限制条件

• $2 \leq N \leq 250000$
• $N$ 是偶数
• $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$）
• 给定的图是一棵树
• 输入的所有数值均为整数

样例解释 1

输出样例的操作顺序如下：

• 第 $1$ 次操作：删除顶点 $4, 1$。剩下的树包含顶点 $2, 3$，仍然存在完全匹配。该操作的得分为 $3$。
• 第 $2$ 次操作：删除顶点 $2, 3$。剩下的树为 $0$ 个顶点，仍然存在完全匹配。该操作的得分为 $1$。
• 总得分为 $3+1=4$。无法使总得分超过 $4$，因此该输出是正确的。

由 ChatGPT 4.1 翻译