At the Sirius Educational Center, one can observe not only common frogs but also tree frogs, some of which are known to be able to change their color from green to brown and vice versa.

As is well known, a tree is a connected graph without cycles. Each vertex of the tree is initially occupied by exactly one frog. All frogs are initially green. Frogs can jump along the tree. In a single jump, a frog moves from the vertex it is currently in to an adjacent vertex connected by an edge. After each jump, the frog's color changes to the opposite one.

Frogs love to form duets. A duet must consist of two frogs of different colors. For two frogs to form a duet, one of the frogs must reach the vertex where the other frog is located, having made no more than $d$ jumps. For the guest's color to differ from the host's color after the movement, the guest must make an odd number of jumps.

You need to determine the maximum number of frog duets that can be formed. Each frog can be part of only one duet. If you correctly determine the maximum number of duets, you will receive partial points for the subtask. To receive full points for the subtask, you must also specify which pairs of frogs should form duets to achieve this maximum number.

Input

The first line of the input contains a single integer $n$ ($2 \leqslant n \leqslant 5 \cdot 10^5$) — the number of vertices in the tree.

The second line of the input contains a single odd integer $d$ ($1 \leqslant d \leqslant n - 1$) — the maximum number of jumps one frog can make to reach another.

Each of the following $n - 1$ lines contains two integers $u$ and $v$ ($1 \leqslant u, v \leqslant n$) — the indices of the tree vertices connected by an edge. The vertices are numbered from $1$ to $n$.

Output

In the first line, output a single integer $m$ — the maximum possible number of frog duets that can be formed.

If you do not wish to provide the pairs themselves, output $-1$ in the next line and terminate the program.

Otherwise, in the following $m$ lines, output two integers $u_i$ and $v_i$ — the pair of vertices whose frogs should meet at one of these vertices and form a duet, following the rules described above.

If the maximum number of duets can be formed in several ways, output any of them.

Subtasks

Examples

Input 1

8
7
1 2
2 3
3 4
3 5
1 6
6 7
3 8

Output 1

3
2 7
6 3
4 1

Input 2

11
3
1 2
2 3
3 4
3 5
3 6
3 7
1 8
8 9
8 10
8 11

Output 2

4
3 7
11 8
10 2
1 6

Figure 1. Tree frogs, one green and one brown, on a tree branch.