2669. [HAOI 2017]新型城市化

【题目描述】

Anihc 国有 $n$ 座城市。城市之间存在一些贸易合作关系，如果城市 $x$ 与城市 $y$ 之间存在贸易协定，那么城市 $x$ 和城市 $y$ 则是一对贸易伙伴(注意： $(x,y)$ 和 $(y,x)$) 是同一对城市)。

为了实现新型城市化，实现统筹城乡一体化以及发挥城市群辐射与带动作用，国家决定规划新型城市关系。一些城市能够被称为城市群的条件是：这些城市两两都是贸易伙伴。由于Anihc 国之前也一直很重视城市关系建设，所以可以保证在目前已存在的贸易合作关系的情况下 Anihc 的 $n$ 座城市可以恰好被划分为不超过两个城市群。

为了建设新型城市关系 Anihc 国想要选出两个之前并不是贸易伙伴的城市，使这两个城市成为贸易伙伴，并且要求在这两个城市成为贸易伙伴之后，最大城市群的大小至少比他们成为贸易伙伴之前的最大城市群的大小增加 1。

Anihc 国需要在下一次会议上讨论扩大建设新型城市关系的问题，所以要请你求出在哪些城市之间建立贸易伙伴关系可以使得这个条件成立，即建立此关系前后的最大城市群的大小至少相差 1。

【输入格式】

第一行 2 个整数 $n,m$，表示城市的个数，目前还没有建立贸易伙伴关系的城市的对数。

接下来 $m$ 行，每行 2 个整数 $x,y$ 表示城市 $x,y$ 之间目前还没有建立贸易伙伴关系。

【输出格式】

第一行一个整数Ans，表示符合条件的城市的对数，注意$(x,y)$与$(y,x)$算同一对城市。

接下来Ans行，每行两个整数，表示一对可以选择来建立贸易伙伴关系的城市。对于一对城市$x,y$请先输出编号更小的那一个。最后城市对与城市对之间的顺序请按照字典序从小到大输出。

【样例输入】

5 3
1 5
2 4
2 5

【样例输出】

2
1 5
2 4

【提示】

数据规模与约定

数据点$1：n≤16$；

数据点$2：n≤16$；

数据点$3$~$5$：$n≤100$；

数据点$6$：$n≤500$；

数据点$7$~$10$：$n≤10000$；

对于所有的测试数据保证：$n\leq 10000,0\leq m\leq \min(150000,\frac{n(n-1)}{2},1\leq x,y\leq n$，保证输入的城市关系中不会出现$(x,x)$这样的关系，同一对城市也不会出现两次(无重边，无自环)。

【来源】

$2017$河南省选 上午$t1$