Dado un árbol, añade tantas aristas como sea posible de modo que el grafo resultante sea un grafo cactus.

Un grafo cactus es un grafo donde cada arista está contenida en, a lo sumo, un ciclo simple. Este grafo no puede contener bucles (self-loops) ni aristas paralelas.

Entrada

La primera línea contiene un entero $N$, el tamaño del árbol ($1 \le N \le 200\,000$).

Cada una de las siguientes $N - 1$ líneas contiene dos enteros $u$ y $v$ ($1 \le u, v \le N, u \neq v$), indicando que hay una arista entre los nodos $u$ y $v$. Se garantiza que el grafo resultante es un árbol.

Salida

En la primera línea, imprime $K$, el número máximo de aristas que se pueden añadir al grafo. En cada una de las siguientes $K$ líneas, imprime dos enteros $a$ y $b$ ($1 \le a, b \le N, a \neq b$), indicando que vas a añadir una arista entre los nodos $a$ y $b$. El grafo resultante debe ser un grafo cactus.

Si existen varias soluciones con el máximo $K$ posible, imprime cualquiera de ellas.

Ejemplos

Entrada 1

6
6 4
3 1
3 6
4 5
2 3

Salida 1

2
2 1
3 5