快递寡头

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Berland 的道路网是一张无向简单图。两家快递公司都需要在任意两座城市之间安排各自的路线，并且两条路线不能共用道路。原道路网保证满足这一要求，也就是原图是 2-边连通图。

政府希望废弃一些道路，同时仍让保留下来的图保持 2-边连通。请输出需要保留的最少道路数，并给出任意一组达到最少道路数的方案。

输入格式

第一行包含两个整数 $n,m$，分别表示城市数和道路数。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示城市 $u$ 与城市 $v$ 之间有一条无向道路。

输入保证没有自环和重边，并保证原图 2-边连通。

输出格式

第一行输出一个整数 $k$，表示最少需要保留的道路数。

接下来输出 $k$ 行，每行两个整数 $u,v$，表示保留道路 $(u,v)$。

若最优方案不唯一，输出任意一组即可；道路的顺序以及每条道路两个端点的顺序均不限。

样例输入 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

数据范围

对于所有数据，$3\le n\le14$，$n\le m\le\frac{n(n-1)}2$，$1\le u,v\le n$。

说明

评测器会检查输出的每条道路确实存在于输入图中、没有重复，并检查保留后的图连通且没有桥，同时检查道路数达到最优值。

下图对应原题样例，红色边表示一种保留方案。