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.