题目描述

题目译自 XV OI Olimpiada Informatyczna – III etap Podział Królestwa

拜托西亚有 $n$ 个城市（$n$ 为偶数），通过 $m$ 条道路连接。需将城市划分为两部分，每部分含 $n/2$ 个城市，且包含城市 1 的部分需明确输出。目标是使连接两部分的道路数量（需建造哨所的道路）最少。

输入格式

1. 第一行：两个整数 $n, m$（$2 \leq n \leq 26$，$n$ 为偶数，$0 \leq m \leq n(n-1)/2$），分别表示城市数和道路数；
2. 接下来 $m$ 行：每行两个整数 $u_i, v_i$（$1 \leq u_i < v_i \leq n$），表示城市 $u_i$ 和 $v_i$ 间有道路。

输出格式

输出一行，包含 $n/2$ 个整数（升序排列），表示包含城市 1 的那部分城市编号。

样例

输入

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

输出

1 2 6