Pour un arbre enraciné $A$ et un entier $B \ge 2$, on définit l'arbre non enraciné $A * B$ comme suit :

• On crée $B$ copies de l'arbre $A$, notées $A_1, A_2, \ldots, A_B$, puis pour tout $i$ tel que $1 \le i < B$, on ajoute une arête reliant la racine de $A_i$ à la racine de $A_{i+1}$.

Étant donné un arbre non enraciné $C$, trouvez un arbre enraciné $A$ et un entier $B \ge 2$ tels que $C = A * B$.

Il est garanti qu'il existe toujours au moins un arbre enraciné $A$ et un entier $B \ge 2$ tels que $C = A * B$.

Si plusieurs solutions existent, vous pouvez en afficher n'importe laquelle.

Pour deux arbres non enracinés $T_1$ et $T_2$, on considère que $T_1 = T_2$ si les deux arbres ont la même structure, indépendamment de la numérotation des sommets.

Entrée

La première ligne contient le nombre de sommets $N$ de l'arbre $C$. $(2 \le N \le 100\,000)$

Les $N-1$ lignes suivantes contiennent chacune deux entiers $u$ et $v$ séparés par un espace, représentant les extrémités d'une arête de l'arbre $C$. $(1 \le u, v \le N)$

Sortie

La première ligne doit contenir l'entier $B$.

La deuxième ligne doit contenir le nombre de sommets $M$ de l'arbre $A$.

Les $M-1$ lignes suivantes doivent contenir chacune deux entiers $u$ et $v$ séparés par un espace, représentant les extrémités d'une arête de l'arbre $A$. $(1 \le u, v \le M)$

La racine de l'arbre $A$ est le sommet $1$.

Exemples

Entrée 1

4
1 2
2 3
3 4

Sortie 1

4
1

Entrée 2

6
1 2
1 3
1 4
4 5
4 6

Sortie 2

2
3
1 2
1 3