CF1155F.Delivery Oligopoly

The whole delivery market of Berland is controlled by two rival companies: BerEx and BerPS. They both provide fast and reliable delivery services across all the cities of Berland.

The map of Berland can be represented as an undirected graph. The cities are vertices and the roads are edges between them. Each pair of cities has no more than one road between them. Each road connects different cities.

BerEx and BerPS are so competitive that for each pair of cities $(v, u)$ they have set up their paths from $v$ to $u$ in such a way that these two paths don't share a single road. It is guaranteed that it was possible.

Now Berland government decided to cut down the road maintenance cost by abandoning some roads. Obviously, they want to maintain as little roads as possible. However, they don't want to break the entire delivery system. So BerEx and BerPS should still be able to have their paths between every pair of cities non-intersecting.

What is the minimal number of roads Berland government can maintain?

More formally, given a 2-edge connected undirected graph, what is the minimum number of edges that can be left in it so that the resulting graph is also 2-edge connected?

贝尔兰的整个快递市场由两家竞争公司控制：BerEx 和 BerPS。它们均在贝尔兰所有城市间提供快速可靠的快递服务。

贝尔兰的地图可表示为一个无向图：城市是顶点，道路是连接它们的边。任意两个城市之间至多只有一条道路，且每条道路连接两个不同的城市。

BerEx 和 BerPS 的竞争如此激烈，以至于对每一对城市 $(v, u)$，它们各自设置了从 $v$ 到 $u$ 的路径，且这两条路径不共享任何一条道路。题目保证这样的设置是可行的。

现在，贝尔兰政府决定通过废弃部分道路来降低道路维护成本。显然，他们希望保留的道路数量尽可能少。然而，他们又不希望破坏整个快递系统。因此，BerEx 和 BerPS 仍须能为每一对城市分别提供两条互不相交（即不共享任何边）的路径。

贝尔兰政府最少需要保留多少条道路？

更形式化地：给定一个 2-边连通 的无向图，最少保留多少条边，可使得剩余图仍为 2-边连通？

The first line contains two integers $n$ and $m$ ($3 \le n \le 14$, $n \le m \le \frac{n(n - 1)}{2}$) — the number of cities and the number of roads between them.

Each of the next $m$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$, $v \ne u$) — the cities connected by the next road.

It is guaranteed that each pair of cities has no more than one road between them. It is guaranteed that each pair of cities have at least two paths between them that don't share a single road.

第一行包含两个整数 $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$）—— 表示由下一条道路连接的两个城市。

保证任意两个城市之间至多只有一条道路。保证任意两个城市之间至少存在两条不共享任何一条道路的路径。

The first line should contain a single integer $k$ — the minimum number of roads Berland government can maintain so that BerEx and BerPS are still able to have their paths between every pair of cities non-intersecting.

The next $k$ lines should contain the list of roads which are being maintained. Each line of form "$v~u$", where $v$ and $u$ are cities connected by the next road.

If there are multiple lists of minimum size, print any of them. The order of roads in the list doesn't matter.

第一行应包含一个整数 $k$ —— Berland 政府能够维持的最少道路数量，使得 BerEx 和 BerPS 仍能在每对城市之间拥有互不相交的路径。

接下来的 $k$ 行应列出被维持的道路。每行格式为 "$v~u$"，其中 $v$ 和 $u$ 是由该道路连接的两个城市。

若存在多个满足最小规模的道路列表，输出任意一个即可。列表中道路的顺序无关紧要。

Here are graphs from the examples, red edges are the maintained ones.

以下是示例中的图，红色边为被保留的边。