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.
Z drugiej strony, Król Bajtazar wie, że jeśli pozwoli w jednym mieście otworzyć filie
obu gildii, to zapewne doprowadzi to do zmowy gildii i zmonopolizowania rynku odzieżowego.
Dlatego też poprosił Cię o pomoc.
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.