루트 있는 트리 $A$와 $2$ 이상의 정수 $B$에 대해 루트 없는 트리 $A * B$를 다음과 같이 정의한다.

• 트리 $A$를 $B$회 복제하여 $B$개의 트리 $A_1, A_2, \ldots, A_B$를 만든 뒤 ($1$ 이상 $B$ 미만인) 모든 $i$에 대해 $A_i$의 루트와 $A_{i+1}$의 루트를 간선으로 잇는다.

루트 없는 트리 $C$가 주어질 때 $C = A*B$인 루트 있는 트리 $A$와 $2$ 이상의 정수 $B$를 구하시오.

$C = A*B$인 루트 있는 트리 $A$와 $2$ 이상의 정수 $B$가 존재하는 경우만 주어진다.

가능한 답이 여러 개 존재할 경우 그 중 아무 것이나 출력한다.

루트 없는 두 트리 $T_1$, $T_2$에 대해 두 트리의 정점 번호를 무시하고 $T_1$과 $T_2$의 모양이 같다면 $T_1 = T_2$이다.

Input

첫 번째 줄에 트리 $C$의 정점의 개수 $N$이 주어진다. $(2 \le N \le 100\,000)$

두 번째 줄부터 $N-1$개의 줄에 걸쳐 각 줄에 트리 $C$의 간선의 끝점 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N)$

Output

첫 번째 줄에 정수 $B$를 출력한다.

두 번째 줄에 트리 $A$의 정점의 개수 $M$을 출력한다.

세 번째 줄부터 $M-1$개의 줄에 걸쳐 각 줄에 트리 $A$의 간선의 끝점 $u$, $v$를 공백으로 구분하여 출력한다. $(1 \le u, v \le M)$

트리 $A$의 루트는 정점 $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