Автор: | Жюри зимних сборов 2009 | Ограничение времени: | 8 сек | |
Входной файл: | half.in | Ограничение памяти: | 64 Мб | |
Выходной файл: | half.out | |||
Максимальный балл: | 100 |
Дан неориентированный граф из n вершин, где n чётно. Необходимо разбить вершины графа на два равных по размеру множества так, чтобы количество рёбер с концами в разных множествах было минимально.
Первая строка содержит два целых числа n и m — количество вершин и рёбер графа (2≤n≤30, n чётно).
Следующие m строк содержат описания рёбер — каждое ребро задано номерами своих концов. Вершины нумеруются с единицы. Гарантируется, что в графе нет кратных рёбер и петель.
Выведите в первую строку выходного файла через пробел номера n2 вершин, которые входят в одно из множеств оптимального разбиения вместе с первой вершиной. Вершины должны быть перечислены в порядке возрастания номеров. Если оптимальных разбиений несколько, то разрешается вывести любое.
№ | Входной файл (half.in ) |
Выходной файл (half.out ) |
---|---|---|
1 |
|
|