CF1396E.Distance Matching

You are given an integer $k$ and a tree $T$ with $n$ nodes ($n$ is even).

Let $dist(u, v)$ be the number of edges on the shortest path from node $u$ to node $v$ in $T$.

Let us define a undirected weighted complete graph $G = (V, E)$ as following:

• $V = {x \mid 1 \le x \le n }$ i.e. the set of integers from $1$ to $n$
• $E = {(u, v, w) \mid 1 \le u, v \le n, u \neq v, w = dist(u, v) }$ i.e. there is an edge between every pair of distinct nodes, the weight being the distance between their respective nodes in $T$

Your task is simple, find a perfect matching in $G$ with total edge weight $k$ $(1 \le k \le n^2)$.

给你一个整数 $k$ 和一棵包含 $n$ 个节点的树 $T$（$n$ 为偶数）。

令 $dist(u, v)$ 表示树 $T$ 中从节点 $u$ 到节点 $v$ 的最短路径上的边数。

我们按如下方式定义一个无向带权完全图 $G = (V, E)$：

• $V = \{x \mid 1 \le x \le n\}$，即从 $1$ 到 $n$ 的所有整数构成的集合；
• $E = \{(u, v, w) \mid 1 \le u, v \le n,\, u \neq v,\, w = dist(u, v)\}$，即对任意两个不同的节点 $u$ 和 $v$，均存在一条连接它们的边，其权重为它们在 $T$ 中的距离 $dist(u, v)$。

你的任务很简单：在 $G$ 中找出一个总边权恰好为 $k$（其中 $1 \le k \le n^2$）的完美匹配。

The first line of input contains two integers $n$, $k$ ($2 \le n \le 100\,000$, $n$ is even, $1 \le k \le n^2$): number of nodes and the total edge weight of the perfect matching you need to find.

The $i$-th of the following $n - 1$ lines contains two integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$) denoting an edge between $v_i$ and $u_i$ in $T$. It is guaranteed that the given graph is a tree.

输入的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 100\,000$，$n$ 为偶数，$1 \le k \le n^2$）：分别为节点数，以及你需要找到的完美匹配的总边权。

接下来的 $n - 1$ 行中，第 $i$ 行包含两个整数 $v_i$、$u_i$（$1 \le v_i, u_i \le n$），表示树 $T$ 中节点 $v_i$ 与 $u_i$ 之间的一条边。保证所给图是一棵树。

If there are no matchings that satisfy the above condition, output "NO" (without quotes) on a single line.

Otherwise, you should output "YES" (without quotes) on the first line of output.

You should then output $\frac{n}{2}$ lines, the $i$-th line containing $p_i, q_i$ ($1 \le p_i, q_i \le n$): the $i$-th pair of the matching.

如果不存在满足上述条件的匹配，则在单独一行输出 “NO”（不带引号）。

否则，应在输出的第一行输出 “YES”（不带引号）。

然后，应输出 $\frac{n}{2}$ 行，其中第 $i$ 行包含 $p_i, q_i$（$1 \le p_i, q_i \le n$）：匹配中的第 $i$ 对。

A tree is a connected acyclic undirected graph.

A matching is set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex.

A perfect matching is a matching which matches all vertices of the graph; that is, every vertex of the graph is incident to exactly one edge of the matching.

树是一个连通的无环无向图。

匹配是一组两两不相邻的边（不含自环），即任意两条边不共享公共顶点。

完美匹配是一种匹配，它覆盖图中的所有顶点；即图中的每个顶点恰好与匹配中的一条边关联。