Score : $550$ points

问题陈述

给定一个有 $N$ 个顶点的树 $T$。顶点编号为 $1$ 到 $N$，第 $i$ 条边 $(1 \leq i \leq N-1)$ 双向连接顶点 $u_i$ 和 $v_i$。

使用 $T$ 定义一个有 $N$ 个顶点的完全图 $G$，如下：

• 在 $G$ 中，顶点 $x$ 和 $y$ 之间的边的权重 $w(x,y)$ 是在 $T$ 中顶点 $x$ 和 $y$ 之间的最短距离。

在 $G$ 中找到一个 最大权重最大匹配。也就是说，找到一组 $\lfloor N/2 \rfloor$ 对顶点 $M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\}$，使得每个顶点 $1,2,\dots, N$ 在 $M$ 中最多出现一次，并且 $\displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i)$ 最大化。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a tree $T$ with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$-th edge $(1 \leq i \leq N-1)$ connects vertices $u_i$ and $v_i$ bidirectionally.

Using $T$, define a complete graph $G$ with $N$ vertices as follows:

• The weight $w(x,y)$ of the edge between vertices $x$ and $y$ in $G$ is the shortest distance between vertices $x$ and $y$ in $T$.

Find one maximum weight maximum matching in $G$. That is, find a set of $\lfloor N/2 \rfloor$ pairs of vertices $M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\}$ such that each vertex $1,2,\dots, N$ appears in $M$ at most once, and $\displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i)$ is maximized.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N$
• The input graph is a tree.
• All input values are integers.

Input

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

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

Output

Print a solution as $\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\}$ in the following format. If multiple solutions exist, any of them is acceptable.

$x_1$ $y_1$

$x_2$ $y_2$

$\vdots$

$x_{\lfloor N/2 \rfloor}$ $y_{\lfloor N/2 \rfloor}$

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2 4
1 3

In $T$, the distance between vertices $2$ and $4$ is $2$, and the distance between vertices $1$ and $3$ is $2$, so the weight of the matching $\{(2,4),(1,3)\}$ is $4$. There is no matching with a weight greater than $4$, so this is a maximum weight maximum matching. Other acceptable outputs include:

2 3
1 4

Sample Input 2

3
1 2
2 3

Sample Output 2

1 3

In $T$, the distance between vertices $1$ and $3$ is $2$, so the weight of the matching $\{(1,3)\}$ is $2$. There is no matching with a weight greater than $2$, so this is a maximum weight maximum matching. Another acceptable output is:

3 1