# [POI2008]POD-Subdivision of Kingdom

## 题目描述

Byteasar, king of Byteotia, has finally decided to retire. He has two sons, however, and is unable to decide which one one of them should succeed him. Therefore he plans to split the kingdom into two halves, making each son a ruler. After the division, watchtowers have to be built along the roads connecting the halves. Obviously, building them will be costly, so ideally there should be as little roads between the halves as possible. Luckily, Byteotia consists of an even number of towns, connected by roads. Resulting from the division, each half-kingdom should contain half the towns. Each road connects (directly) two towns. The roads do not meet nor cross outside towns, though they can lead through flyovers or tunnels. Every two towns are directly connected by at most one road. Which exact towns should lie in which half of the kingdom is a matter of great importance. You may assume that the land outside the towns can be partitioned in such a way that the roads connecting towns lying in the same half will not cross the border. On the other hand, one watchtower has to be built by each road connecting towns from different halves. Task Write a programme that: reads the descriptions of towns and the roads connecting them from the standard input, determines such a partition of kingdom into halves that both the halves contain an equal number of towns and the number of roads connecting towns lying in different halves is minimum, writes out the result to the standard output. If more than one optimum partition exists, your programme should pick one of them arbitrarily. 给定一个n个点的无向图，要求将点集分成大小相等的两个子集，使两个子集之间的边数最少

## 输入输出格式

### 输入格式

The first line of the standard input contains two integers ![](http://main.edu.pl/images/OI15/pod-en-tex.1.png) and ![](http://main.edu.pl/images/OI15/pod-en-tex.2.png), separated by a single space, denoting the number of towns and number of roads respectively, ![](http://main.edu.pl/images/OI15/pod-en-tex.3.png), ![](http://main.edu.pl/images/OI15/pod-en-tex.4.png), ![](http://main.edu.pl/images/OI15/pod-en-tex.5.png). The towns are numbered from ![](http://main.edu.pl/images/OI15/pod-en-tex.6.png) to ![](http://main.edu.pl/images/OI15/pod-en-tex.7.png). Each of the following ![](http://main.edu.pl/images/OI15/pod-en-tex.8.png) lines contains two integers separated by a single space. The line no. ![](http://main.edu.pl/images/OI15/pod-en-tex.9.png) (for ![](http://main.edu.pl/images/OI15/pod-en-tex.10.png)) contains the numbers ![](http://main.edu.pl/images/OI15/pod-en-tex.11.png) and ![](http://main.edu.pl/images/OI15/pod-en-tex.12.png), ![](h…

### 输出格式

Your programme should write out exactly one line to the standard output. It should contain ![](http://main.edu.pl/images/OI15/pod-en-tex.16.png) integers separated by single spaces. These should be the numbers of towns belonging to the same half of the kingdom the town no. ![](http://main.edu.pl/images/OI15/pod-en-tex.17.png) does, in an increasing order.

## 输入输出样例

### 输入样例 #1

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

### 输出样例 #1

``````1 2 6
``````