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