Podział Królestwa

Limit pamięci: 32 MB

Król Bajtocji Bajtazar postanowił przejść na emeryturę. Ma on dwóch synów. Nie może się jednak zdecydować, który z nich powinien być jego następcą. Postanowił więc podzielić królestwo na dwie połowy i uczynić swoich synów ich władcami.

Po podziale królestwa, na drogach łączących obie połowy należy zbudować strażnice. Ponieważ wiąże się to z kosztami, dróg łączących obie połowy powinno być możliwie najmniej.

Bajtocja składa się z parzystej liczby miast połączonych drogami. W wyniku podziału, w każdej połowie powinna znaleźć się połowa miast. Każda droga łączy dwa miasta. Drogi nie łączą ani nie krzyżują się poza miastami, mogą natomiast występować wiadukty tudzież tunele. Każde dwa miasta mogą być bezpośrednio połączone co najwyżej jedną drogą.

Przy podziale królestwa istotne jest, które miasta znajdą się w której połowie. Możesz założyć, że teren poza miastami można tak podzielić, że drogi łączące miasta leżące w tej samej połowie nie będą przecinać granicy. Natomiast na każdej drodze łączącej miasta z różnych połówek trzeba wybudować jedną strażnicę.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis miast i łączących je dróg,
• wyznaczy taki podział królestwa na dwie połowy, że w każdej połowie będzie tyle samo miast, a liczba dróg łączących miasta leżące w różnych połowach będzie minimalna,
• wypisze wyznaczony wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia zapisane są dwie liczby całkowite i oddzielone pojedynczym odstępem, równe odpowiednio liczbie miast i liczbie łączących je dróg, , , . Miasta są ponumerowane od 1 do . W kolejnych wierszach zapisane są po dwie liczby całkowite oddzielone pojedynczym odstępem. W wierszu -szym (dla ) zapisane są liczby i , . Reprezentują one drogę łączącą miasta i .

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający liczb całkowitych pooddzielanych pojedynczymi odstępami. Powinny to być numery miast należących do tej połówki królestwa, do której należy miasto nr 1, podane w rosnącej kolejności.

Przykład

Dla danych wejściowych:

6 8
1 2
1 6
2 3
2 5
2 6
3 4
4 5
5 6

poprawną odpowiedzią jest:

1 2 6

Na rysunku linią przerywaną zaznaczono optymalny podział, który wymaga zbudowania 3 strażnic.

Autor zadania: Zbigniew Czech.