Byteotia 的国王 Byteasar 终于决定退位了。然而他有两个儿子，无法决定由谁来继承王位。因此，他计划将王国一分为二，让每个儿子各统治一半。

划分完成后，必须在连接两个半区的道路上修建岗哨。显然，修建岗哨的成本很高，因此理想情况下，两个半区之间的道路数量应尽可能少。

幸运的是，Byteotia 由偶数个城镇组成，城镇之间由道路连接。划分后，每个半王国应包含一半的城镇。每条道路（直接）连接两个城镇。道路在城镇之外不会相交，尽管它们可以通过立交桥或隧道。任意两个城镇之间最多直接由一条道路连接。

具体哪些城镇属于哪一半王国至关重要。你可以假设城镇之外的土地可以进行划分，使得连接同一半区内城镇的道路不会穿过边界。另一方面，每一条连接不同半区城镇的道路上都必须修建一个岗哨。

编写一个程序：

• 从标准输入读取城镇及其连接道路的描述，
• 确定一种将王国划分为两半的方案，使得两个半区包含的城镇数量相等，且连接不同半区城镇的道路数量最少，
• 将结果输出到标准输出。

如果存在多个最优划分方案，你的程序可以任意选择其中一个。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$，由一个空格分隔，分别表示城镇的数量和道路的数量，$2 \le n \le 26$，$2 \mid n$，$0 \le m \le \frac{n\cdot(n-1)}{2}$。城镇编号从 $1$ 到 $n$。接下来的 $m$ 行，每行包含两个由空格分隔的整数。第 $(i+1)$ 行（对于 $i=1,2,\dots,m$）包含数字 $u_i$ 和 $v_i$，$1 \le u_i < v_i \le n$，表示连接 $u_i$ 和 $v_i$ 的一条道路。

输出格式

你的程序应向标准输出写入一行。该行应包含 $\frac{n}{2}$ 个由空格分隔的整数。这些数字应为与 1 号城镇属于同一半王国的城镇编号，并按升序排列。

样例

输入 1

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

输出 1

1 2 6

图中的虚线显示了最优划分方案，该方案所需的岗哨数量最少。