#1130. [POI2008]POD Subdivision of Kingdom

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

6 8  

1 2  

1 6  

2 3  

2 5  

2 6  

3 4  

4 5  

5 6

样例输出

1 2 6

数据范围与提示

N<=26