codeforces#P1155F. Delivery Oligopoly
Delivery Oligopoly
Description
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?
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.
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.
Input
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.
Output
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.
Samples
3 3
1 2
2 3
3 1
3
1 3
3 2
1 2
4 5
1 2
1 4
2 3
4 3
1 3
4
1 4
4 3
3 2
1 2
6 10
1 2
2 3
3 1
3 4
4 5
5 6
4 6
2 5
1 6
3 5
6
1 6
6 5
5 4
4 3
3 2
1 2
Note
Here are graphs from the examples, red edges are the maintained ones.
