Ustalanie relacji filogenetycznych między organizmami jest bardzo ważnym zadaniem bioinformatyki.

Relacje filogenetyczne zwykle przedstawia się za pomocą drzewa, zwanego drzewem filogenetycznym. Każdy organizm odpowiada liściowi w tym drzewie.

Długość ścieżki między dwoma liśćmi w drzewie filogenetycznym określa stopień pokrewieństwa ewolucyjnego odpowiadających im organizmów.

Na podstawie drzewa filogenetycznego można zdefiniować graf przedstawiający stopień pokrewieństwa ewolucyjnego organizmów.

Graf ten nazywamy grafem filogenetycznym.

Graf filogenetyczny o podobieństwie $K$ definiujemy następująco.

Wierzchołki grafu reprezentują organizmy. Krawędź między dwoma wierzchołkami istnieje wtedy i tylko wtedy, gdy odległość (długość ścieżki) między odpowiadającymi im węzłami drzewa filogenetycznego nie przekracza $K$.

Laboratorium zbudowało graf filogenetyczny o podobieństwie $3$, a następnie utraciło dane drzewa filogenetycznego. Chce zatem odtworzyć to drzewo.

Mając graf filogenetyczny o podobieństwie $3$, napisz program, który znajdzie drzewo filogenetyczne definiujące ten graf.

Zwróć uwagę, że graf wejściowy jest zawsze spójny i na pewno istnieje odpowiadające mu drzewo filogenetyczne.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $N$ ($2 \le N \le 5000$), oznaczającą liczbę wierzchołków grafu filogenetycznego.

Wierzchołki są ponumerowane od $1$ do $N$.

Drugi wiersz zawiera liczbę całkowitą $M$ ($1 \le M \le 1000000$), oznaczającą liczbę krawędzi grafu filogenetycznego.

Każdy z następnych $M$ wierszy zawiera dwie liczby całkowite $v,w$ ($1 \le v,w \le N$), oznaczające końce jednej krawędzi grafu filogenetycznego.

Wyjście

W pierwszym wierszu wypisz liczbę $S$ krawędzi drzewa filogenetycznego.

W każdym z następnych $S$ wierszy wypisz numery końców krawędzi, $v$ i $w$, oddzielone jedną spacją.

Krawędzie drzewa można wypisać w dowolnej kolejności.

Jednak numery węzłów od $1$ do $N$ muszą być przypisane liściom.

Ponadto wierzchołek grafu wejściowego i odpowiadający mu liść drzewa filogenetycznego muszą mieć ten sam numer.

Pozostałym węzłom wewnętrznym można dowolnie przypisać numery od $N+1$ do $S+1$. Jeśli istnieje więcej niż jedno drzewo filogenetyczne, znajdź i wypisz dowolne z nich.

Przykład

Wejście 1

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

Wyjście 1

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

Za zaliczenie wszystkich testów przyznaje się 100 punktów, w przeciwnym razie 0 punktów.