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)$ .

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.

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.

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.