In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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ę.
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 .
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.
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.