Distance Matching
Description
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.
Input
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.
Output
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.
Samples
4 2
1 2
2 3
3 4
YES
2 1
3 4
4 4
1 2
2 3
3 4
YES
3 1
2 4
Note
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.