有 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