Arseny 喜欢组织聚会并邀请人们参加。然而,参加他聚会的不仅是朋友,还有他朋友的朋友、他朋友的朋友的朋友等等。这就是为什么阿尔森尼的一些客人他可能不认识。他决定使用以下过程来解决此问题。
在每一步中,他都会选择一位客人 A,他两两互相介绍他所有的朋友。执行此操作后,A 的任意两个朋友都成为朋友。这个过程一直持续到所有客人都成为朋友为止。
Arseny 不想花太多时间来做这件事,所以他想用最少的步骤完成这个过程。帮助阿森尼做到这一点。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 22; $$0 \leq m \leq \frac{n(n-1)}{2}$$) — 聚会上的客人人数(包括 Arseny)和朋友的人数。
接下来的 m 行每行包含两个整数 u 和 v(1 ≤ u,v ≤ n;u ≠ v),这意味着数字 u 和 v 的人最初是朋友。保证每对朋友被描述不超过一次并且友谊图是相连的。
输出
在第一行中打印出使所有客人成为朋友所需的最少步骤数。
在第二行中打印每一步选择的客人的 ID。
如果有多个解,则可以输出任意一个。
示例
输入 #1
5 6 1 2 1 3 2 3 2 5 3 4 4 5
输出 #1
2 2 3
输入 #2
4 4 1 2 1 3 1 4 3 4
输出 #2
1 1
注意
在第一个测试用例中,没有任何客人是所有其他客人的朋友,因此至少需要两个步骤来执行该任务。当第二位客人两两介绍了他所有的朋友后,只有一对客人(4, 1)和(4, 2)不是朋友。客人3或5可以介绍他们。
在第二个测试用例中,1号客人是所有客人的朋友,因此他可以一步一步两两介绍所有客人。