Polish version    English version  
  O olimpiadzie -> Zadania


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

Zadanie: SPO
Autor: Wojciech Rytter
Spokojna komisja

Zawody II stopnia, dzień pierwszy 7 luty 2001
Plik źródłowy: SPO.??? (np. pas, c, cpp)
Plik wykonywalny: SPO.exe
Plik wejściowy: SPO.in
Plik wyjściowy: SPO.out

W parlamencie Demokratycznej Republiki Bajtocji, zgodnie z Bardzo Ważną Ustawą, należy ukonstytuować Komisję Poselską do Spraw Spokoju Publicznego. Niestety sprawę utrudnia fakt, iż niektórzy posłowie wzajemnie się nie lubią.

Komisja musi spełniać następujące warunki:

  • każda partia ma dokładnie jednego reprezentanta w Komisji,
  • jeśli dwaj posłowie się nie lubią, to nie mogą jednocześnie być w Komisji.
Każda partia ma w parlamencie dokładnie dwóch posłów. Wszyscy posłowie są ponumerowani liczbami od 1 do 2n. Posłowie o numerach 2i-1 i 2i należą do partii o numerze i.

Zadanie

Napisz program, który:
  • wczyta z pliku tekstowego SPO.IN liczbę partii oraz pary posłów, którzy się wzajemnie nie lubią,
  • wyznaczy skład Komisji, lub stwierdzi, że nie da się jej ukonstytuować,
  • zapisze wynik w pliku tekstowym SPO.OUT.

Wejście

W pierwszym wierszu pliku tekstowego SPO.IN znajdują się dwie nieujemne liczby całkowite n i m. Liczba n, spełniająca warunki 1<=n<=8000, oznacza liczbę partii. Liczba m, spełniająca warunki 0<=m<=20000, oznacza liczbę par nielubiących się posłów. W każdym z kolejnych m wierszy zapisana jest para liczb naturalnych a i b, 1<=a<b<=2n, oddzielonych pojedynczym odstępem. Oznacza ona, że posłowie o numerach a i b wzajemnie się nie lubią.

Wyjście

Plik tekstowy SPO.OUT powinien zawierać pojedyncze słowo NIE, jeśli utworzenie Komisji nie jest możliwe. W przypadku, gdy utworzenie Komisji jest możliwe, plik SPO.OUT powinien zawierać n liczb całkowitych z przedziału od 1 do 2n, zapisanych w kolejności rosnącej i oznaczających numery posłów zasiadających w Komisji. Każda z tych liczb powinna zostać zapisana w osobnym wierszu. Jeśli Komisję można utworzyć na wiele sposobów, Twój program może wypisać dowolny z nich.

Przykład

Dla pliku wejściowego SPO.IN:
3 2
1 3
2 4
poprawną odpowiedzią jest plik wyjściowy SPO.OUT:
1
4
5



Wersja do druku