Étant donné un arbre, ajoutez autant d'arêtes que possible de sorte que le graphe résultant soit un graphe cactus.

Un graphe cactus est un graphe où chaque arête appartient à au plus un cycle simple. Ce graphe ne doit pas contenir de boucles (self-loops) ni d'arêtes parallèles.

Entrée

La première ligne contient un entier $N$, la taille de l'arbre ($1 \le N \le 200\,000$).

Chacune des $N - 1$ lignes suivantes contient deux entiers $u$ et $v$ ($1 \le u, v \le N$, $u \neq v$), indiquant qu'il existe une arête entre les nœuds $u$ et $v$. Il est garanti que le graphe résultant est un arbre.

Sortie

Sur la première ligne, affichez $K$, le nombre maximum d'arêtes pouvant être ajoutées au graphe. Sur chacune des $K$ lignes suivantes, affichez deux entiers $a$ et $b$ ($1 \le a, b \le N$, $a \neq b$), indiquant que vous ajoutez une arête entre les nœuds $a$ et $b$. Le graphe résultant doit être un graphe cactus.

S'il existe plusieurs solutions avec le maximum possible $K$, affichez-en n'importe laquelle.

Exemples

Entrée 1

6
6 4
3 1
3 6
4 5
2 3

Sortie 1

2
2 1
3 5