B. A Problem You Will Hate More Than Yourself
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Shaaban found the contestants eager to participate in the competition and solve educational problems, so he wanted to disappoint everyone and give them the following problem.

You are given a tree consisting of $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. You need to add the minimum number of vertices to the tree such that the following conditions are satisfied after all additions:

  • the graph must still be a tree;
  • the longest path in the tree must consist of an even number of vertices;
  • there must be exactly $$$k$$$ distinct such longest paths.

Two paths are considered different if there exists at least one vertex which belongs to exactly one of the two paths.

Print the minimum number of vertices you have to add, then print the edges you added.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^6)$$$ — the number of vertices in the tree, and the desired length of the longest paths.

Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le n, u \neq v)$$$ — the description of the edges of the tree. It's guaranteed that the given edges form a valid tree.

Output

Print a single integer $$$m$$$, representing the minimum number of vertices you have to add.

For each of the next $$$m$$$ lines, print two integers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le n + m)$$$ — representing an edge you added to the tree.

Example
Input
3 3
1 2
2 3
Output
3
2 4
2 5
1 6
Note
The final graph, where the length of the longest path is even, and the number of such longest paths is exactly $$$3$$$. All longest paths are: $$$(4,1), (4,5), (4,6)$$$.