Das Ermitteln phylogenetischer Beziehungen zwischen Organismen ist eine sehr wichtige Aufgabe der Bioinformatik.

Phylogenetische Beziehungen werden gewöhnlich durch einen Baum dargestellt, den man phylogenetischen Baum nennt. Jeder Organismus entspricht einem Blattknoten dieses Baums.

Die Länge des Pfads zwischen zwei Blattknoten im phylogenetischen Baum gibt an, wie eng die entsprechenden Organismen evolutionär verwandt sind.

Anhand eines phylogenetischen Baums lässt sich ein Graph definieren, der den Grad der evolutionären Verwandtschaft zwischen Organismen darstellt.

Diesen Graphen nennen wir phylogenetischen Graphen.

Ein phylogenetischer Graph mit Ähnlichkeit $K$ ist wie folgt definiert.

Die Knoten des Graphen stellen die Organismen dar. Zwischen zwei Knoten gibt es genau dann eine Kante, wenn der Abstand (die Pfadlänge) zwischen ihren entsprechenden Knoten im phylogenetischen Baum höchstens $K$ beträgt.

Ein Labor erstellte einen phylogenetischen Graphen mit Ähnlichkeit $3$ und verlor anschließend die Daten des phylogenetischen Baums. Daher soll der Baum rekonstruiert werden.

Schreibe ein Programm, das zu einem gegebenen phylogenetischen Graphen mit Ähnlichkeit $3$ einen phylogenetischen Baum findet, der diesen Graphen definiert.

Beachte, dass der Eingabegraph immer zusammenhängend ist und ein entsprechender phylogenetischer Baum garantiert existiert.

Eingabe

Die erste Zeile enthält eine ganze Zahl $N$ ($2 \le N \le 5000$), die Anzahl der Knoten des phylogenetischen Graphen.

Die Knoten sind von $1$ bis $N$ nummeriert.

Die zweite Zeile enthält eine ganze Zahl $M$ ($1 \le M \le 1000000$), die Anzahl der Kanten des phylogenetischen Graphen.

Jede der folgenden $M$ Zeilen enthält zwei ganze Zahlen $v,w$ ($1 \le v,w \le N$), die Endknoten einer Kante des phylogenetischen Graphen.

Ausgabe

Gib in der ersten Zeile die Anzahl $S$ der Kanten des phylogenetischen Baums aus.

Gib in jeder der folgenden $S$ Zeilen die Endknotennummern $v$ und $w$ einer Kante aus, getrennt durch ein Leerzeichen.

Die Baumkanten dürfen in beliebiger Reihenfolge ausgegeben werden.

Die Knotennummern $1$ bis $N$ müssen jedoch den Blättern zugewiesen werden.

Außerdem müssen jeder Knoten des Eingabegraphen und sein entsprechendes Blatt im phylogenetischen Baum dieselbe Nummer haben.

Die übrigen inneren Knoten dürfen beliebig mit den Nummern $N+1$ bis $S+1$ versehen werden. Falls mehrere phylogenetische Bäume existieren, finde einen beliebigen davon und gib ihn aus.

Beispiele

Eingabe 1

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

Ausgabe 1

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

Wenn alle Tests bestanden werden, gibt es 100 Punkte, andernfalls 0 Punkte.