Gildie
Limit pamięci: 64 MB
Król Bajtazar ma nie lada problem. Gildia Szwaczek oraz Gildia Krawców jednocześnie poprosiły o pozwolenie na otwarcie swoich filii w każdym z miast królestwa.
W Bajtocji jest miast.
Niektóre z nich są połączone dwukierunkowymi drogami.
Każda z gildii wysunęła postulat, aby dla każdego miasta:
- znajdowała się w nim filia danej gildii, lub
- miasto było bezpośrednio połączone drogą z miastem, w którym znajduje się filia tej gildii.
Wejście
W pierwszym wierszu standardowego wejścia podane są dwie liczby całkowite oraz
(
,
), oznaczające odpowiednio liczbę miast
i liczbę dróg w Bajtocji.
Miasta są ponumerowane od
do
.
W
-szym wierszu wejścia znajduje się opis
-tej drogi;
zawiera on liczby
oraz
(
,
) oznaczające, że
-ta droga łączy miasta
oraz
.
Każda para miast jest połączona co najwyżej jedną drogą.
Drogi nie krzyżują się - jedynie mogą spotykać się w miastach - choć mogą prowadzić tunelami i estakadami.
Wyjście
W pierwszym wierszu standardowego wyjścia Twój program powinien wypisać jedno słowo:
TAK - jeśli da się rozmieścić filie gildii w miastach zgodnie z warunkami zadania lub
NIE - w przeciwnym przypadku.
W przypadku odpowiedzi TAK, w kolejnych wierszach powinien znaleźć się opis przykładowego
rozmieszczenia filii.
-szy wiersz powinien zawierać:
-
literę K, jeśli w mieście
ma się znaleźć filia gildii krawców, lub
-
literę S, jeśli w mieście
ma się znaleźć filia gildii szwaczek, lub
-
literę N, jeśli w mieście
nie ma się znaleźć filia żadnej z dwóch gildii.
Przykład
Dla danych wejściowych:
7 8 1 2 3 4 5 4 6 4 7 4 5 6 5 7 6 7
poprawną odpowiedzią jest:
TAK K S K S K K N
Miasta, w których ma zostać otwarta gildia krawców, są zaznaczone kółkami, a te, w których ma zostać otwarta gildia szwaczek, są zaznaczone rombami.
Autor zadania: Marcin Pilipczuk.