410017 - 新型城市化

有 n(n ≤ 10^4)座城市。两城之间有贸易协定则互为贸易伙伴;一个城市群指两两都是贸易伙伴的点集。题目保证:当前贸易关系下,n 座城市可恰好划分为不超过两个城市群。 现在要从当前不是贸易伙伴的城市对中选一对,让他们成为贸易伙伴,并要求最大城市群的大小至少增加 1。求所有可行的城市对。

输入

第一行 n, m(0 ≤ m ≤ min(1.5×10^5, n(n − 1) / 2):城市数、当前非贸易伙伴的对数。 接下来 m 行,每行 x, y:城市 x 与 y 目前不是贸易伙伴(无重边无自环)。

输出

第一行 ans:可行对数。 接下来 ans 行,每行 u v(u < v),按字典序输出。

样例

输入

5 3
1 5
2 4
2 5

输出

2
    1 5
2 4
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题