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.
Jeżeli istnieje wiele poprawnych podziałów królestwa, Twój program
powinien wyznaczyć którykolwiek z nich.
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.