Para un árbol con raíz $A$ y un entero $B \ge 2$, definimos el árbol sin raíz $A * B$ de la siguiente manera:

• Se crean $B$ copias del árbol $A$, denotadas como $A_1, A_2, \ldots, A_B$. Luego, para todo $i$ tal que $1 \le i < B$, se conecta la raíz de $A_i$ con la raíz de $A_{i+1}$ mediante una arista.

Dado un árbol sin raíz $C$, encuentre un árbol con raíz $A$ y un entero $B \ge 2$ tales que $C = A * B$.

Se garantiza que siempre existe al menos un par $(A, B)$ tal que $C = A * B$.

Si existen múltiples soluciones, puede imprimir cualquiera de ellas.

Dos árboles sin raíz $T_1$ y $T_2$ se consideran iguales ($T_1 = T_2$) si tienen la misma estructura, ignorando las etiquetas de los vértices.

Entrada

La primera línea contiene el número de vértices $N$ del árbol $C$. $(2 \le N \le 100\,000)$

Las siguientes $N-1$ líneas contienen los extremos $u, v$ de cada arista del árbol $C$, separados por un espacio. $(1 \le u, v \le N)$

Salida

La primera línea debe contener el entero $B$.

La segunda línea debe contener el número de vértices $M$ del árbol $A$.

Las siguientes $M-1$ líneas deben contener los extremos $u, v$ de cada arista del árbol $A$, separados por un espacio. $(1 \le u, v \le M)$

La raíz del árbol $A$ es el vértice $1$.

Ejemplos

Entrada 1

4
1 2
2 3
3 4

Salida 1

4
1

Entrada 2

6
1 2
1 3
1 4
4 5
4 6

Salida 2

2
3
1 2
1 3