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.