| O olimpiadzie -> Zadania |  |
|
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.
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 4poprawną odpowiedzią jest plik wyjściowy SPO.OUT:
1 4 5