W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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 . Miasto nr 1 leży na zachodnim, a nr 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 -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:
W pierwszym wierszu standardowego wejścia zapisane są dwie liczby całkowite - liczba miast i liczba planowanych autostrad , . W kolejnych wierszach zapisane są pary miast, które mają zostać połączone autostradami. W wierszu zapisane są dwie liczby całkowite , oddzielone pojedynczym odstępem - numery miast, które ma połączyć -ta autostrada, . 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ć wierszy. W -tym wierszu należy wypisać jedną wielką literę, odpowiednio N - jeśli autostrada łącząca miasta 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.
Dla danych wejściowych:
8 7 1 2 1 3 2 4 5 7 4 8 7 8 6 8
poprawną odpowiedzią jest:
N N S S S N N
Autor zadania: Tomasz Waleń.