Królestwo

Limit pamięci: 128 MB

W Bajtorii jest miast i parzysta liczba dwukierunkowych dróg łączących miasta. Sieć dróg umożliwia przejazd pomiędzy dowolnymi dwoma miastami królestwa.

Król Bajtor, władca Bajtorii, znany jest ze swojego zamiłowania do liczb parzystych. Gdy zorientował się, że w jego królestwie istnieją miasta, z których wychodzi nieparzysta liczba dróg, natychmiast zażądał rozbudowy sieci dróg.

Doradca króla zna dobrze finanse Bajtorii i wie, że realizacja tak poważnej inwestycji uniemożliwiłaby organizację Zimowych Igrzysk Olimpijskich, jakże oczekiwanych przez bajtorski lud. Planuje więc przekonać króla, że Bajtoria ma wystarczająco dużo "parzystych" walorów i poprosić o odłożenie inwestycji na przyszły rok.

Po pierwsze, doradca zaskoczy króla faktem, że w Bajtorii istnieje parzyście wiele miast o nieparzystej liczbie dróg wychodzących. Następnie podzieli te miasta w pary i dla każdej z utworzonych par wyznaczy trasę z do , składającą się z parzystej liczby dróg. Aby jeszcze bardziej zadziwić króla, żadna droga nie pojawi się więcej niż raz na trasie z do . Ponadto, żadna droga Bajtorii nie będzie wchodzić w skład więcej niż jednej z wyznaczonych tras.

Doradca jest pewien, że takie argumenty przekonają króla. Nie może jednak poradzić sobie z faktycznym wyznaczeniem tras, dlatego poprosił Ciebie o pomoc.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (). Oznaczają one odpowiednio liczbę miast oraz liczbę dróg w Bajtorii. jest liczbą parzystą.

Każdy z kolejnych wierszy zawiera dwie liczby całkowite (), oznaczające, że miasta i są połączone dwukierunkową drogą. Między dowolnymi dwoma miastami może istnieć co najwyżej jedna droga.

Można założyć, że istnieje miasto, z którego wychodzi nieparzysta liczba dróg.

Wyjście

Oznaczmy przez liczbę miast, z których wychodzi nieparzysta liczba dróg (doradca jest pewien, że jest liczbą parzystą).

Jeżeli nie jest możliwe wyznaczenie tras według planu doradcy, w jedynym wierszu wyjścia należy wypisać słowo NIE.

W przeciwnym wypadku należy wypisać opisów wyznaczonych tras. Każdy z opisów tras powinien składać się z dwóch wierszy. W pierwszym wierszu -tego opisu powinny znaleźć się trzy liczby całkowite () oznaczające, że trasa zaczyna się w , kończy w i składa się z dróg. W drugim wierszu -tego opisu powinno znaleźć się liczb całkowitych, oznaczających numery kolejnych dróg na trasie. Drogi ponumerowane są liczbami od do , według kolejności w jakiej podano je wejściu.

Jeśli istnieje wiele rozwiązań, Twój program może wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

6 8
1 2
2 3
3 4
4 5
5 6
6 1
1 4
2 5

poprawną odpowiedzią jest:

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

Autor zadania: Maciej Klimek.