Estabelecer relações filogenéticas entre organismos é uma tarefa muito importante em bioinformática.

As relações filogenéticas são normalmente representadas por uma árvore, chamada árvore filogenética. Cada organismo corresponde a uma folha da árvore filogenética.

O comprimento do caminho entre duas folhas na árvore filogenética indica o grau de parentesco evolutivo dos organismos correspondentes.

A partir de uma árvore filogenética, pode definir-se um grafo que representa o grau de parentesco evolutivo entre os organismos.

Este grafo chama-se grafo filogenético.

Um grafo filogenético com similaridade $K$ define-se da seguinte forma.

Os vértices do grafo representam os organismos. Existe uma aresta entre dois vértices se e só se a distância (comprimento do caminho) entre os nós correspondentes na árvore filogenética for no máximo $K$.

Um laboratório construiu um grafo filogenético com similaridade $3$ e depois perdeu os dados da árvore filogenética. Por isso, pretende reconstruir a árvore.

Dado um grafo filogenético com similaridade $3$, escreve um programa que encontre uma árvore filogenética que defina este grafo.

Nota que o grafo de entrada é sempre conexo e é garantida a existência de uma árvore filogenética correspondente.

Entrada

A primeira linha contém um inteiro $N$ ($2 \le N \le 5000$), o número de vértices do grafo filogenético.

Os vértices são numerados de $1$ a $N$.

A segunda linha contém um inteiro $M$ ($1 \le M \le 1000000$), o número de arestas do grafo filogenético.

Cada uma das $M$ linhas seguintes contém dois inteiros $v,w$ ($1 \le v,w \le N$), os extremos de uma aresta do grafo filogenético.

Saída

Na primeira linha, imprime o número $S$ de arestas da árvore filogenética.

Em cada uma das $S$ linhas seguintes, imprime os números $v$ e $w$ dos extremos de uma aresta, separados por um espaço.

As arestas da árvore podem ser impressas em qualquer ordem.

Contudo, os números de nó de $1$ a $N$ devem ser atribuídos às folhas.

Além disso, cada vértice do grafo de entrada e a folha correspondente na árvore filogenética devem ter o mesmo número.

Os restantes nós internos podem ser numerados arbitrariamente de $N+1$ a $S+1$. Se existir mais de uma árvore filogenética, encontra e imprime qualquer uma delas.

Exemplos

Entrada 1

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

Saída 1

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

São atribuídos 100 pontos se todos os testes forem superados; caso contrário, 0 pontos.