Description

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.

Input Format

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 Format

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.

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

1 2 6

Hint

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