|
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