E. Distance Matchingtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou 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).InputThe 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. OutputIf 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.ExamplesInput
4 2
1 2
2 3
3 4
Output
YES
2 1
3 4
Input
4 4
1 2
2 3
3 4
Output
YES
3 1
2 4
NoteA 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.
4 2
1 2
2 3
3 4

YES 2 1 3 4 
['constructive algorithms', 'dfs and similar', 'trees', '*3200']