← 返回题目列表

Codeforces · 1155/F

F. 交付寡头垄断

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

Berland 的整个配送市场由两家竞争对手公司控制:BerEx 和 BerPS。他们都在伯兰所有城市提供快速、可靠的送货服务。

Berland 地图可以表示为无向图。城市是顶点,道路是它们之间的边。每对城市之间最多只有一条道路。每条道路连接不同的城市。

BerEx 和 BerPS 的竞争非常激烈,以至于对于每对城市 $$$(v, u)$$$,他们都设置了从 $$$v$$$ 到 $$$u$$$ 的路径,使得这两条路径不共享一条道路。可以保证这是可能的。

现在贝尔兰政府决定通过放弃一些道路来降低道路维护成本。显然,他们希望维护尽可能少的道路。然而,他们不想破坏整个传输系统。因此,BerEx 和 BerPS 应该仍然能够在每对城市之间建立不相交的路径。

Berland 政府至少可以维护多少条道路?

更正式地说,给定一个 2 边连通的无向图,其中可以保留的最小边数是多少,以便生成的图也是 2 边连通的?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 14$$$, $$$n \le m \le \frac{n(n - 1)}{2}$$$) — 城市数量及其之间的道路数量。

接下来的 $$$m$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \ne u$$$) — 由下一条道路连接的城市。

保证每对城市之间的道路不超过一条。保证每对城市之间至少有两条不共享一条道路的路径。

输出

第一行应包含一个整数 $$$k$$$ — Berland 政府可以维护的最小道路数量,以便 BerEx 和 BerPS 仍然能够在每对城市之间保持不相交的路径。

接下来的 $$$k$$$ 行应包含正在维护的道路列表。每行形式为“$$$v~u$$$”,其中$$$v$$$和$$$u$$$是由下一条道路连接的城市。

如果有多个最小尺寸列表,则打印其中任何一个。列表中道路的顺序并不重要。

示例

输入 #1

3 3
1 2
2 3
3 1

输出 #1

3
1 3
3 2
1 2

输入 #2

4 5
1 2
1 4
2 3
4 3
1 3

输出 #2

4
1 4
4 3
3 2
1 2

输入 #3

6 10
1 2
2 3
3 1
3 4
4 5
5 6
4 6
2 5
1 6
3 5

输出 #3

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

注意

这是示例中的图表,红色边缘是保留的边缘。