Minimum Cross-Edges Partitioning

Given an undirected graph with $n$ vertices and $m$ edges, you are required to determine a legal partition of the vertices into two groups containing exactly $\frac{n}{2}$ vertices each, such that the number of edges with endpoints in different groups is minimized.

Formally, let $G=(V,E)$ be an undirected graph with $|V|=n$ and $|E|=m$. You need to find a subset $S \subset V$ with $|S| = \frac{n}{2}$ so that the number of edges crossing between $S$ and $V\setminus S$ is minimized.

inputFormat

The first line contains two integers $n$ and $m$, where $n$ is an even number.

The following $m$ lines each contain two integers $u$ and $v$, denoting an undirected edge between vertices $u$ and $v$ (1-indexed).

outputFormat

Output the vertices (1-indexed) belonging to the first group of the partition, separated by spaces. This group must contain exactly $\frac{n}{2}$ vertices and the chosen partition should minimize the number of edges with endpoints in different groups.

sample

4 4
1 2
2 3
3 4
4 1

1 3