X Olimpiada Informatyczna 2002/2003
|
Zadanie: aut
|
Autor: Tomasz Waleń
|
Zawody II stopnia, dzień pierwszy |
Plik źródłowy: | aut.xxx (xxx=pas,c,cpp) |
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 23-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.
Napisz program, który:
Limit pamięci dla tego zadania wynosi 32 MB.
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 pi, qi oddzielone pojedynczym odstępem - numery miast, które ma połączyć i-ta autostrada, 1 <= pi < qi <= n. Pary miast w danych wejściowych nie powtarzają się.
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 pi i qi 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.
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