[POI2008] POD-Subdivision of Kingdom
题目背景
[English Edition](/paste/eu7u3hqg)
题目描述
给出一张有 $n$ 个点 $m$ 条边的无向图,你需要求出一组合法的方案,使得图被划分为点数均为 $\frac n2$ 的两个集合,且两个端点在不同集合中的边数最少。
输入输出格式
输入格式
第一行两个整数 $n,m$。
之后 $m$ 行,每行两个整数 $a, b$,表示在 $a$ 与 $b$ 之间有一条边。
输出格式
一行 $\frac n2$ 个整数,表示在你求出的方案中的一个集合的所有点,由编号从小到大排序。
输入输出样例
输入样例 #1
6 8
1 2
1 6
2 3
2 5
2 6
3 4
4 5
5 6
输出样例 #1
1 2 6
说明
对于 $100\%$ 的数据,$1\le n\le 26$,$1\le a,b\le n$,且 $n$ 为偶数。保证没有重边。