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

Условие

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

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

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

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

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

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

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

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

1 2 6