W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
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 .
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ą.
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.