AT_arc183_d.[ARC183D] Keep Perfectly Matched

有一棵包含 $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$ 次操作中选择的两个顶点。如果有多种方案，输出任意一种均可。

限制条件

• $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 翻译