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
注意
这是示例中的图表,红色边缘是保留的边缘。