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.