English
Zadanie Zagadka [A] (zag)
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.