For a rooted tree $A$ and an integer $B \ge 2$, we define an unrooted tree $A * B$ as follows:

• Create $B$ copies of tree $A$, denoted as $A_1, A_2, \ldots, A_B$. For every $i$ such that $1 \le i < B$, connect the root of $A_i$ and the root of $A_{i+1}$ with an edge.

Given an unrooted tree $C$, find a rooted tree $A$ and an integer $B \ge 2$ such that $C = A * B$.

It is guaranteed that there exists at least one rooted tree $A$ and an integer $B \ge 2$ such that $C = A * B$.

If there are multiple possible answers, you may output any one of them.

Two unrooted trees $T_1$ and $T_2$ are considered equal ($T_1 = T_2$) if they are isomorphic, ignoring vertex labels.

Input

The first line contains the number of vertices $N$ of the tree $C$. $(2 \le N \le 100\,000)$

The next $N-1$ lines each contain two space-separated integers $u$ and $v$, representing the endpoints of an edge in tree $C$. $(1 \le u, v \le N)$

Output

The first line should contain the integer $B$.

The second line should contain the number of vertices $M$ of the tree $A$.

The next $M-1$ lines each should contain two space-separated integers $u$ and $v$, representing the endpoints of an edge in tree $A$. $(1 \le u, v \le M)$

The root of tree $A$ is vertex $1$.

Examples

Input 1

4
1 2
2 3
3 4

Output 1

4
1

Input 2

6
1 2
1 3
1 4
4 5
4 6

Output 2

2
3
1 2
1 3