3545. 修路

单测试点时限: 2.0 秒

内存限制: 256 MB

ultmaster 男神由于夜晚要到他的小迷妹们寝室楼辅导小迷妹们学习,为了方便,他决定在小迷妹们的寝室楼之间修一些有向道路,使得可以从 号寝室楼到 号寝室楼(不一定要直接在 之间修路)。他想知道他至少要修几条路。

你需要输出修路的方案。如有多组解输出任意一组解。

输入

第一行两个整数 分别表示小迷妹寝室楼的个数以及需要满足联通的个数。

之后 行,每行两个整数 表示 号寝室楼到 号寝室楼。保证有序数对 只会在输入中最多出现一次。

输出

第一行一个整数 ,表示最少需要修几条路。

之后 行,每行两个整数 ,表示从 修一条有向道路。

样例

Input
2 1
1 2
Output
1
1 2
Input
3 3
1 2
2 1
1 3
Output
3
1 2
2 3
2 1

提示

样例二解释:从 1 到 3 可以通过 1 到 2 再 2 到 3 到达。

11 人解决,23 已尝试。

13 份提交通过,共有 101 份提交。

8.8 EMB 奖励。

创建: 8 月,2 周前.

修改: 7 月,4 周前.

最后提交: 3 月前.

来源: EOJ Monthly 2018.4

标签