POlitycy

04.11.2010
TrudnośćTrudnośćTrudnośćTrudność

POlitycy

Limit czasowy: 1000 milisekund
Limit pamięciowy: 16000 kilobajtów


Kolejne wybory parlamentarne za nami. Pierwszym zadaniem świeżo upieczonego premiera Rydzia jest stworzenie rządu. Premier Rydzio zdecydował, że wyboru dokona spośród n członków własnej partii. Niestety, każdy kandydat na ministra przekazał Rydziowi listę kolegów z partii, z którymi nie ma zamiaru pracować razem w rządzie (zakładamy, że jeżeli osoba A nie chce pracować z osobą B to także B nie chce pracować z A). Co więcej, każdy z posłów zagroził, że jeżeli nie zostanie wybrany to zasili szeregi opozycji. W takiej sytuacji stworzenie rządu było oczywiście niemożliwe - potrzebny był natychmiastowy kompromis.

Nie zastanawiając się zbyt długo, premier Rydzio zaproponował następujące rozwiązanie:
a) Tylko część kandydatów znajdzie się w rządzie. Pozostali trafią do rady nadzorczej Bardzo Ważnej Spółki.
b) Zarówno w rządzie jak i w radzie nadzorczej nie zasiądą 3 osoby, które nie chcą ze sobą pracować. Innymi słowy, nie będzie takich trzech osób A,B,C, że A nie chce pracować z B i C, B nie chce pracować z C oraz A,B,C otrzymały nominację do tej samej instytucji.

Wszystko byłoby dobrze, gdyby nie jeden problem - premier Rydzio nie ma najmniejszego pojęcia jak podzielić kandydatów między rządem, a radą nadzorczą. Co więcej, lider opozycji publicznie obwieścił, że on nie widzi w tym żadnego problemu i nie wyobraża sobie jak taki ktoś jak Rydzio może być premierem. Stwierdził on także, że gdyby nie wszyscy kandydaci musieliby zostać wybrani, to on umie zaproponować taki podział, że zarówno w rządzie, radzie nadzorczej i grupie niewybranych członków partii Rydzia nie ma dwóch osób, które nie chcą ze sobą pracować.

Los kraju jest w Twoich rękach. Pomóż Rydziowi uniknąć dymisji rozwiązując jego problem! Możesz założyć, że lider opozycji mówi prawdę.  

Wejście:

W pierwszej linii znajdują się dwie liczby n (1<=n<=100) i m. Jest to odpowiednio liczba członków partii Rydzia oraz liczba par kandydatów, którzy nie chcą ze sobą pracować. Dalej na wejściu pojawia się m par liczb. W i-tej z nich znajdują się dwie liczby a,b (0<=a<b<n). Oznaczają one, że posłowie o numerach a i b nie chcą ze sobą pracować. Wszystkie pary liczb są różne. 

Wyjście:

W pierwszej linii Twój program powinien wypisać dwie liczby t i k (0<=t,k<=n, t+k=n) oddzielone pojedynczą spacją. Jest to odpowiednio liczba posłów w rządzie i radzie nadzorczej. W drugiej linii powinno znaleźć się t liczb oddzielonych pojedynczym odstępem. Są to numery posłów, którzy zasiądą w rządzie. W trzeciej linii Twój program powinien wypisać k liczb oddzielonych pojedynczym odstępem. Są to numery posłów, którzy zasiądą w radzie nadzorczej Bardzo Ważnej Spółki. Jeżeli istnieje wiele rozwiązań Twój program może wypisać dowolne z nich.  

Przykład

Dla danych przykładowych:
7 11
0 1
0 2
0 4
1 2
1 3
2 5
3 5
3 4
4 5
2 6
5 6

jedną z poprawych odpowiedzi jest:
3 4
3 5 1
0 2 4 6

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com