Polish version    English version  
  Historia OI -> X OI 2002/2003 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
X Olimpiada Informatyczna 2002/2003

Zadanie: aut
Autor: Tomasz Waleń
Autostrady

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.

Sieć kolejowa

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).

Przykładowy plan

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 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ę.

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 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.

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



Wersja do druku