P3475 [POI 2008] POD-Subdivision of Kingdom

[English Edition](/paste/eu7u3hqg)

Given an undirected graph with $n$ vertices and $m$ edges, you need to find a valid partition of the vertices into two sets, each of size $\frac{n}{2}$, such that the number of edges whose endpoints lie in different sets is minimized.

The first line contains two integers $n, m$. Then follow $m$ lines, each containing two integers $a, b$, indicating that there is an edge between $a$ and $b$.

Output one line with $\frac{n}{2}$ integers: all vertices in one of the sets from your partition, sorted in increasing order by their labels.

For $100\%$ of the testdata, $1 \le n \le 26$, $1 \le a, b \le n$, and $n$ is even. It is guaranteed that there are no multiple edges. Translated by ChatGPT 5