SP10265 DIVIDEKR - Subdivision of the kingdom

Byteasar 是 Byteotia 的国王，如今他想要退位。他有两个儿子，但不知道该让谁继承王位，因此决定将王国一分为二，每个儿子管理一半。 为了保障边境的安全，两个半国之间的道路上需要建造瞭望塔。然而，建造这些塔的费用极高，所以我们的目标是尽量减少这类连接道路的数量。 幸运的是，整个 Byteotia 由偶数个城镇组成，并且这些城镇通过道路连接。完成分割后，每个半国应该包含相同数量的城镇。每条道路直接连接两个城镇，且它们在城镇外不会相交或交叉，即使它们通过立交桥或隧道相连。任意两个城镇最多只有一条直接连接的道路。 在分割过程中哪些城镇应该在哪个半国是非常关键的。你可以放心，城镇之间的道路可以被合理分区，使得同一半国内的道路不会穿越边界。而对于连接不同半国内的任意两城镇的道路，则必须建造瞭望塔。 ---- ### 任务 编写一个程序来： - 读取由城镇和道路构成的地图描述； - 确定一种分割方式，使得两半国各包含相同数量的城镇，并且跨越两半国的道路数量最少； - 输出结果。 如果存在多种最优分割方案，那么程序可以选择其中任意一种输出。

第一行有两个整数 $n$ 和 $m$，分别表示城镇数量和道路数量，$2 \leq n \leq 26$，$1 \leq m \leq \frac{n \cdot (n - 1)}2$，且 $n$ 是偶数。城镇编号从 $1$ 到 $n$。 接下来的 $m$ 行中，每行包含两个整数 $a_i$ 和 $b_i$，表示一条连接城镇 $a_i$ 和 $b_i$ 的道路，$1 \leq a_i < b_i \leq n$。

输出一行，包含 $\frac{n}2$ 个整数，用空格分隔。这些整数表示与城镇 $1$ 在同一半国的城镇编号，按升序排列。

 上图中虚线表示的即是最优分割方案，这样只需建造两座瞭望塔。 --- **本翻译由 AI 自动生成**，由 [1277793](https://www.luogu.com.cn/user/1277793) 修缮。