Codeforces Round 666 (Div. 1) |
---|
Finished |
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:
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.
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
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.
Name |
---|