黑暗爆炸OJ

DARKBZOJ

#1130. [POI2008]POD Subdivision of Kingdom

Statistics 下载数据

Description

给出一个具有N个结点的无向图,将其分成两个集合S1,S2. 这两个集合的点的个数一样多,但连接它们的边最少.

Input

第一行给出数字N,M,代表有N个点,M条边. 下面M行,每行两个数字代表此两点间有条边.

Output

输出的点集应包含1，且按升序排列

Sample Input

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

Sample Output

1 2 6

Hint

N<=26

Source

鸣谢VFleaKing提供SPJ