Establecer las relaciones filogenéticas entre organismos es una tarea muy importante en bioinformática.

Las relaciones filogenéticas suelen representarse mediante un árbol, llamado árbol filogenético. Cada organismo corresponde a una hoja del árbol filogenético.

La longitud del camino entre dos hojas del árbol filogenético indica el grado de parentesco evolutivo entre los organismos correspondientes.

A partir de un árbol filogenético se puede definir un grafo que represente el grado de parentesco evolutivo entre los organismos.

Este grafo se llama grafo filogenético.

Un grafo filogenético de similitud $K$ se define de la siguiente manera.

Los vértices del grafo representan los organismos. Existe una arista entre dos vértices si y solo si la distancia (longitud del camino) entre sus nodos correspondientes en el árbol filogenético es como máximo $K$.

Un laboratorio construyó un grafo filogenético de similitud $3$ y después perdió los datos del árbol filogenético. Por ello quiere reconstruir el árbol.

Dado un grafo filogenético de similitud $3$, escribe un programa que encuentre un árbol filogenético que defina dicho grafo.

Ten en cuenta que el grafo de entrada siempre es conexo y se garantiza que existe un árbol filogenético correspondiente.

Entrada

La primera línea contiene un entero $N$ ($2 \le N \le 5000$), el número de vértices del grafo filogenético.

Los vértices están numerados del $1$ al $N$.

La segunda línea contiene un entero $M$ ($1 \le M \le 1000000$), el número de aristas del grafo filogenético.

Cada una de las siguientes $M$ líneas contiene dos enteros $v,w$ ($1 \le v,w \le N$), los extremos de una arista del grafo filogenético.

Salida

En la primera línea, imprime el número $S$ de aristas del árbol filogenético.

En cada una de las siguientes $S$ líneas, imprime los números $v$ y $w$ de los extremos de una arista, separados por un espacio.

Las aristas del árbol pueden imprimirse en cualquier orden.

Sin embargo, los números de nodo del $1$ al $N$ deben asignarse a las hojas.

Además, cada vértice del grafo de entrada y su hoja correspondiente del árbol filogenético deben tener el mismo número.

Los nodos internos restantes pueden numerarse arbitrariamente del $N+1$ al $S+1$. Si existe más de un árbol filogenético, encuentra e imprime cualquiera de ellos.

Ejemplos

Entrada 1

6
7
1 2
2 3
3 1
3 4
3 5
5 6
6 3

Salida 1

9
1 7
2 7
3 9
4 8
5 10
6 10
7 9
8 9
9 10

Se obtienen 100 puntos si se superan todas las pruebas; en caso contrario, 0 puntos.