← 返回题目列表

Codeforces · 906/C

C. 聚会

中文机器翻译题面 查看原题

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号客人是所有客人的朋友,因此他可以一步一步两两介绍所有客人。