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.