Drogi ekspresowe
Limit pamięci: 64 MB
W Bajtocji jest miast oraz dróg pomiędzy nimi.
Ich jakość jest bardzo kiepska, a ze względu na brak funduszy
drogi od dłuższego czasu nie były remontowane.
Mieszkańcy Bajtocji protestują, domagając się zamiany części
dróg na nowe drogi ekspresowe. Król Bajtocji zarządził, że wybuduje drogi
ekspresowe, ale pod jednym warunkiem. Wystarczy, że zostanie stworzony plan budowy,
w którym z każdego z bajtockich miast będzie wychodziła nieparzysta liczba
dróg ekspresowych. Drogi ekspresowe mogą być budowane tylko w miejscach dróg
już istniejących.
Mieszkańcy poprosili Cię o pomoc w wybraniu odpowiednich dróg. Pomóż mieszkańcom
i stwórz plan budowy dróg ekspresowych lub stwierdź, że taki plan nie istnieje.
Jeśli występuje więcej niż jeden poprawny plan, to wystarczy że podasz dowolny z nich.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (),
oznaczającą liczbę zestawów danych. Dalej podawane są opisy kolejnych zestawów.
Pierwszy wiersz zestawu zawiera dwie liczby całkowite ,
(, ),
oznaczające odpowiednio liczbę miast oraz liczbę dróg w Bajtocji.
W następnych wierszach znajduje się opis połączeń pomiędzy miastami.
Każdy wiersz zawiera dwie liczby całkowite , (),
oznaczające, że miasta i są połączone drogą.
Możesz założyć, że suma we wszystkich zestawach danych nie przekracza ,
a suma nie przekracza .
W testach wartych łącznie puntków zachodzą dodatkowe warunki i .
Wyjście
Na standardowym wyjściu powinny się pojawić odpowiedzi dla kolejnych zestawów danych.
Odpowiedzią dla zestawu danych powinien być opis planu budowy dróg ekspresowych
lub jedno słowo NIE w przypadku, gdy taki plan nie istnieje.
Opis planu powinien zawierać w pierwszym wierszu jedną liczbę całkowitą ,
równą liczbie dróg, które będą zamienione na drogi ekspresowe.
Następnych wierszy powinno opisywać drogi ekspresowe.
Każdy wiersz powinien zawierać dwie liczby całkowite , oznaczające,
że droga pomiędzy miastami i będzie zamieniona na drogę ekspresową.
Przykład
Dla danych wejściowych:
1
6 5
1 2
1 3
2 3
3 4
5 6
poprawną odpowiedzią jest:
4
1 3
2 3
3 4
5 6
Autor zadania: Jacek Tomasiewicz.