题目描述

一种新型无限带宽的无线电通信网络经过测试，已被证实可以替代已无法适应日益增长的流量需求的光纤通信网络。你负责有偿设计这一新型无线电通信网络的布局。当前的通信网络由一些节点组成，这些节点由光纤连接，每根光纤连接两个不同的节点。任意一对节点都至少有一条沿光纤的路径连接它们。但新型的通信网络将不会有任何光纤，由无线连接代替，每条无线连接连接两个节点。无线连接的带宽是无限大的，但也很昂贵，所以无线连接的条数会尽可能少，以保证连通性；每一对节点之间恰好有一条沿无线连接的路径。同时，你还发现每个节点设计时向其他节点的连接数已经确定了下来。如果一个节点与其他节点的连接数发生了改变，这个节点就必须重新搭建，但这很昂贵。

你的任务是设计这个新型网络，在确保每对节点间恰有一条路径的情况下，最小化与原图中连接数不同的节点的数量。下图为样例 1 代表的原始网络和对应的解。

输入格式

第一行有两个整数 $n\ (2 \le n \le 10^4)$ 和 $m\ (1 \le m \le 10^5)$，表示当前网络中的节点数和光纤数。节点从 $0$ 到 $n-1$ 标号。接下来的 $m$ 行每行有两个不同的整数 $a_i$ 和 $b_i$，表示第 $i$ 根光纤连接 $a_i$ 和 $b_i$。保证每一对节点之间至少存在一条路径连接它们。可能存在多于一条光纤连接同一对节点。

输出格式

输出连接数需要改变的节点数量的最小值。从第二行开始，用与输入相同的格式输出无线网络的连接。也就是说，先输出节点的数量（应和输入一样）和无线连接的个数，接下来若干行描述对应的无线连接。如果有多于一种可能的方案，可以输出任意一种。

7 11
0 1
0 2
0 5
0 6
1 3
2 4
1 2
1 2
1 5
2 6
5 6

3
7 6
0 1
0 2
0 5
0 6
3 6
4 6

4 3
0 1
2 1
2 3

0
4 3
2 1
1 3
0 2

数据范围与提示

在不侵犯原题版权的情况下，本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布，注明出处时需指向本题链接。