Distance Matching

2000ms

524288K

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

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.

Sample Input:

Sample Output:

YES
2 1
3 4

Sample Input:

Sample Output:

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.

Informação

Provedor Codeforces

Código CF1396E