Alternatywne formaty: PostScript | PDF

Bajtocja leży na półwyspie. Już od czasów króla Bitola podstawową formą komunikacji w Bajtocji jest transport kolejowy. Król Bitol wybudował jedną super szybką linię kolejową łączącą wschodnie i zachodnie wybrzeże półwyspu. Linia kolejowa przechodzi przez wszystkie miasta Bajtocji, wyznaczając ich numerację - pierwsze miasto na linii ma numer 1, a ostatnie n. Miasto nr 1 leży na zachodnim, a nr n na wschodnim wybrzeżu.

W ostatnich latach, dzięki ministrowi Bajterowiczowi, gospodarka Bajtocji rozwinęła się bardzo gwałtownie i obecna sieć komunikacyjna wymaga szybkiej modernizacji. Król Bajtol zarządził (w ramach kolejnego planu 2³-letniego) budowę wielu autostrad. Każda z autostrad ma łączyć bezpośrednio dwa wybrane miasta Bajtocji. Ze względu na to, że każda autostrada będzie budowana przez oddzielną agencję rządową i na każdej będzie obowiązywał inny rodzaj winiet, zdecydowano, że autostrady nie mogą przecinać się same ze sobą, ani też nie mogą przecinać linii kolejowej. Stąd jedyną możliwością jest zbudowanie autostrad po północnej lub południowej stronie linii kolejowej. Na rysunku 2 przedstawiono przykładowy plan autostrad (autostrady są zaznaczone łukami, a linia kolejowa to łamana składająca się z odcinków).

Najjaśniejszy król Bajtol zdecydował już jakie pary miast mają zostać połączone autostradami. Każda z autostrad opisana jest przez parę miast, które ma łączyć. Twoim zadaniem jest ustalenie dla danego zestawu połączeń, które z autostrad powinny leżeć na północ od linii kolejowej, a które na południe. Pamiętaj jednak że autostrady nie mogą się wzajemnie przecinać, ani też przecinać linii kolejowej.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia informację o planowanych autostradach,
• wyznaczy rozmieszczenie autostrad (lub stwierdzi, że nie da się ich zbudować),
• zapisze wynik na standardowym wyjściu.

Limit pamięci dla tego zadania wynosi 32 MB.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie liczby całkowite - liczba miast n i liczba planowanych autostrad k, 1 <= n,k <= 20000. W kolejnych k wierszach zapisane są pary miast, które mają zostać połączone autostradami. W wierszu i+1 zapisane są dwie liczby całkowite p_i, q_i oddzielone pojedynczym odstępem - numery miast, które ma połączyć i-ta autostrada, 1 <= p_i < q_i <= n. Pary miast w danych wejściowych nie powtarzają się.

Wyjście

Twój program powinien wypisać na standardowe wyjście plan budowy autostrad, lub pojedyncze słowo NIE, jeśli nie jest możliwe zbudowanie wszystkich autostrad. Jeśli budowa autostrad jest możliwa, to na standardowe wyjście należy wypisać k wierszy. W i-tym wierszu należy wypisać jedną wielką literę, odpowiednio N - jeśli autostrada łącząca miasta p_i i q_i ma zostać zbudowana na północ od linii kolejowej, lub S - jeśli na południe od linii kolejowej. Jeśli istnieje wiele możliwych rozwiązań, Twój program powinien wypisać tylko jedno z nich.

Przykład

Dla danych wejściowych:

8 7
1 2
1 3
2 4
5 7
4 8
7 8
6 8

poprawnym wynikiem jest:

N
N
S
S
S
N
N