Zagadka [A]
Limit pamięci: 128 MB
Czarnoksiężnik Voldebajt uwięził rycerza Bitosława Dzielnego.
Zgodnie ze swym okrutnym zwyczajem, obiecał mu wolność w zamian za rozwiązanie
nierozwiązywalnej zagadki.
Ponieważ Bitosław szczególnie dał mu się we znaki, postanowił wymyślić dla niego
coś specjalnie złośliwego.
Oto zagadka, jaką Voldebajt zadał Bitosławowi:
Bajtocja jest podzielona na województw, w których łącznie znajduje się
miast.
Dodatkowo, niektóre pary miast są połączone drogami (dwukierunkowymi).
Chciałbym w każdym województwie wybrać jedno miasto, które będzie jego
stolicą, tak aby każda z istniejących dróg łączyła jakąś stolicę
z innym miastem (potencjalnie także stolicą w innym województwie).
Czy jest to możliwe?
Pomóż Bitosławowi wydostać się z opresji i rozwiąż za niego zagadkę.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite
(), oznaczająca
liczbę miast z zagadki Voldebajta, (),
oznaczająca liczbę dróg, oraz (), oznaczająca
liczbę województw w Bajtocji.
Miasta są ponumerowane od do .
W kolejnych wierszach znajduje się par liczb całkowitych ,
(, ),
z których -ta oznacza drogę łączącą miasta o numerach
oraz .
Żadna para miast nie jest połączona więcej niż jedną drogą.
W kolejnych wierszach znajdują się opisy kolejnych województw.
-ty z tych wierszy rozpoczyna się liczbą (), określającą
liczbę miast w -tym województwie.
Dalej następuje liczb całkowitych
określających (parami różne) numery miast znajdujących się
w -tym województwie.
Suma wszystkich liczb wynosi .
Wyjście
Jeśli odpowiedź na zagadkę jest przecząca, Twój program powinien wypisać
na standardowe wyjście jeden wiersz zawierający słowo NIE.
W przeciwnym razie Twój program powinien wypisać dwa wiersze.
Pierwszy z nich powinien zawierać słowo TAK, drugi zaś opisywać
rozwiązanie zagadki.
W drugim wierszu powinno znaleźć się dokładnie liczb całkowitych.
-ta z nich ma oznaczać numer miasta, które powinno zostać stolicą
-tego województwa.
Jeśli istnieje kilka poprawnych rozwiązań zagadki, Twój program może
wypisać dowolne z nich.
Przykład
Dla danych wejściowych:
6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5
poprawną odpowiedzią jest:
TAK
2 1
natomiast dla danych wejściowych:
3 3 1
1 2
2 3
3 1
3 1 2 3
poprawnym wynikiem jest:
NIE
Autorzy zadania: Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk.