Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Distance Matching

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

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.

Examples

Input

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

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/18/2021 20:22:12 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|