#6413. 「ICPC World Finals 2018」无线光纤

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

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

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

figure.png

输入格式

第一行有两个整数 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 。保证每一对节点之间至少存在一条路径连接它们。可能存在多于一条光纤连接同一对节点。

输出格式

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

样例

样例输入 1

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

样例输出 1

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

样例输入 2

4 3
0 1
2 1
2 3

样例输出 2

0
4 3
2 1
1 3
0 2

数据范围与提示

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