Wstęp do programowania w C++

Jasiu wraz ze swoją wybranką Janiną bardzo lubią podróżować. Tym razem na celowniku mają dobrze znaną podróżnikom Krainę Tysiąca Wysp. Jest to specyficzne miejsce.

Na każdej wyspie znajdują się miasta położone wzdłuż linii brzegowej. Są one połączone drogą, również biegnącą wzdłuż linii brzegowej. Każda wyspa ma nie mniej niż trzy miasta. W środkowej części każdej wyspy znajduje się dziewiczy obszar, który jest niedostępny dla zwiedzających. Wyspy połączone są mostami, z których można podziwiać przepiękne krajobrazy. Mosty są tak zbudowane, aby z każdej wyspy można było dotrzeć do każdej innej dokładnie jedną drogą.

Jasiu ma mało czasu, więc chce skupić się na mostach i stamtąd podziwiać piękne widoki ze swoją wybranką. Niestety na mapach nie jest wyszczególnione, który odcinek łączący dwa miasta jest drogą, a który mostem.

Jako jego dobry kolega pomóż mu i napisz program, który znajdzie wszystkie mosty.

Wejście

W pierwszym wierszu dwie liczby n oraz m określające liczbę miast oraz liczbę dwukierunkowych dróg między nimi (6 ≤ n ≤ 500000; 7 ≤ m ≤ 600000).

W każdym z kolejnych m wierszy znajdują się dwie liczby naturalne a i b (1 ≤ a ≠ b ≤ n) oznaczające, że miasta a i b są połączone dwukierunkową drogą.

Wyjście

Na wyjściu należy wypisać wszystkie pary miast a, b pomiędzy, którymi poprowadzony jest most. Pary miast wypisujemy w kolejności rosnącej. Numery miast w obrębie każdej pary również wypisujemy w kolejności rosnącej.

Przykład

Wejście:

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

Wyjście:

1 9
3 10