Établir les relations phylogénétiques entre des organismes est une tâche très importante en bioinformatique.

Les relations phylogénétiques sont généralement représentées par un arbre, appelé arbre phylogénétique. Chaque organisme correspond à une feuille de l’arbre phylogénétique.

La longueur du chemin entre deux feuilles de l’arbre phylogénétique indique le degré de parenté évolutive des deux organismes correspondants.

À partir d’un arbre phylogénétique, on peut définir un graphe représentant le degré de parenté évolutive entre les organismes.

Ce graphe est appelé graphe phylogénétique.

Un graphe phylogénétique de similarité $K$ est défini comme suit.

Les sommets du graphe représentent les organismes. Une arête existe entre deux sommets si et seulement si la distance (longueur du chemin) entre les nœuds correspondants dans l’arbre phylogénétique est au plus $K$.

Un laboratoire a construit un graphe phylogénétique de similarité $3$, puis a perdu les données de l’arbre phylogénétique. Il souhaite donc reconstruire cet arbre.

Étant donné un graphe phylogénétique de similarité $3$, écrivez un programme qui trouve un arbre phylogénétique définissant ce graphe.

Notez que le graphe d’entrée est toujours connexe et qu’un arbre phylogénétique correspondant existe nécessairement.

Entrée

La première ligne contient un entier $N$ ($2 \le N \le 5000$), le nombre de sommets du graphe phylogénétique.

Les sommets sont numérotés de $1$ à $N$.

La deuxième ligne contient un entier $M$ ($1 \le M \le 1000000$), le nombre d’arêtes du graphe phylogénétique.

Chacune des $M$ lignes suivantes contient deux entiers $v,w$ ($1 \le v,w \le N$), les extrémités d’une arête du graphe phylogénétique.

Sortie

Sur la première ligne, affichez le nombre $S$ d’arêtes de l’arbre phylogénétique.

Sur chacune des $S$ lignes suivantes, affichez les numéros $v$ et $w$ des extrémités d’une arête, séparés par une espace.

Les arêtes de l’arbre peuvent être affichées dans n’importe quel ordre.

Cependant, les numéros de nœuds de $1$ à $N$ doivent être attribués aux feuilles.

De plus, chaque sommet du graphe d’entrée et sa feuille correspondante dans l’arbre phylogénétique doivent porter le même numéro.

Les autres nœuds internes peuvent être numérotés arbitrairement de $N+1$ à $S+1$. Si plusieurs arbres phylogénétiques existent, trouvez et affichez n’importe lequel.

Exemples

Entrée 1

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

Sortie 1

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

Vous obtenez 100 points si tous les tests sont réussis, et 0 sinon.