Задача L. (20081226) Разрез пополам

Автор:Жюри зимних сборов 2009   Ограничение времени:8 сек
Входной файл:half.in   Ограничение памяти:64 Мб
Выходной файл:half.out  
Максимальный балл:100  

Условие

Дан неориентированный граф из n вершин, где n чётно. Необходимо разбить вершины графа на два равных по размеру множества так, чтобы количество рёбер с концами в разных множествах было минимально.

Формат входного файла

Первая строка содержит два целых числа n и m — количество вершин и рёбер графа (2 ≤ n ≤ 30, n чётно).

Следующие m строк содержат описания рёбер — каждое ребро задано номерами своих концов. Вершины нумеруются с единицы. Гарантируется, что в графе нет кратных рёбер и петель.

Формат выходного файла

Выведите в первую строку выходного файла через пробел номера n2 вершин, которые входят в одно из множеств оптимального разбиения вместе с первой вершиной. Вершины должны быть перечислены в порядке возрастания номеров. Если оптимальных разбиений несколько, то разрешается вывести любое.

Примеры тестов

Входной файл (half.in) Выходной файл (half.out)
1
6 8
1 2
6 1
2 3
5 2
2 6
4 3
4 5
6 5
1 2 6

0.102s 0.011s 13