P3731 [HAOI2017] 新型城市化

Anihc 国有 $n$ 座城市。城市之间存在一些贸易合作关系，如果城市 $x$ 与城市 $y$ 之间存在贸易协定，那么城市 $x$ 和城市 $y$ 则是一对贸易伙伴（注意： $(x,y)$ 和 $(y,x)$ 是同一对城市）。 为了实现新型城市化，实现统筹城乡一体化以及发挥城市群辐射与带动作用，国家决定规划新型城市关系。一些城市能够被称为城市群的条件是：这些城市两两都是贸易伙伴。由于Anihc 国之前也一直很重视城市关系建设，所以可以保证在目前已存在的贸易合作关系的情况下 Anihc 的 $n$ 座城市可以恰好被划分为不超过两个城市群。 为了建设新型城市关系 Anihc 国想要选出两个之前并不是贸易伙伴的城市，使这两个城市成为贸易伙伴，并且要求在这两个城市成为贸易伙伴之后，最大城市群的大小至少比他们成为贸易伙伴之前的最大城市群的大小增加 $1$。 Anihc 国需要在下一次会议上讨论扩大建设新型城市关系的问题，所以要请你求出在哪些城市之间建立贸易伙伴关系可以使得这个条件成立，即建立此关系前后的最大城市群的大小至少相差 $1$。

无

无

数据点 $1$：$n\le 16$； 数据点 $2$：$n\le 16$； 数据点 $3\sim 5$：$n\le 100$； 数据点 $6$：$n\le 500$； 数据点 $7\sim10$：$n\le 10^4$。 对于所有的数据保证： $n \le 10^4,0 \le m \le \min(1.5\times 10^5,\dfrac{n(n-1)}{2})$。保证输入的城市关系中不会出现 $(x,x)$ 这样的关系，同一对城市也不会出现两次（无重边，无自环）。