[HAOI2017]新型城市化

题目描述

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

输入输出格式

输入格式


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

输出格式


第一行yi个整数ans,表示符合条件的城市的对数.注意(x,y)与(y,x)算同一对城市。 接下来Ans行,每行两个整数,表示一对可以选择来建立贸易伙伴关系的城市。对于 一对城市x,y请先输出编号更小的那一个。最后城市对与城市对之间顺序请按照字典序从小到大输出。

输入输出样例

输入样例 #1

5 3
1 5
2 4
2 5

输出样例 #1

2
1 5
2 4

说明

数据规模与约定 数据点1: n≤16 数据点2: n≤16 数据点3~5: n≤100 数据点6: n≤500 数据点7~10: n≤10000 对于所有的数据保证:n <= 10000,0 <= m <= min (150000,n(n-1)/2).保证输入的城市关系中不会出现(x,x)这样的关系.同一对城市也不会出现两次(无重边.无自环)。