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.