#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("conexidad.in");
ofstream g("conexidad.out");
long long a[202][202],xx[1001],qq,minim11,c,minim1,minim2,minim22,p,q=0,yy[1001],minim,b[2002],v[1001],m,z1,maxim[10001],z,n,k,j,i,x,y;

void bfs(int start)
{
  int i,k,st,dr;

  st=dr=1;
  b[1]=start;
  v[start]=p;
  while(st<=dr)
  {
    k=b[st];
    for(i=1;i<=n;i++)
      if(v[i]==0 && a[k][i]==1)
      {
        v[i]=p;
        b[++dr]=i;
      }
    st++;
  }

}

int main()
{
    f>>n>>m;
   for(i=1;i<=m;i++)
   {
       f>>x>>y;
       a[x][y]=1;
       a[y][x]=1;
   }
for(i=1;i<=n;i++)
if(v[i]==0)
{p++;
    bfs(i);

}

p=0;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
{if(v[i]!=v[j])
{q=v[j];
    minim1=maxim[i];
    minim11=i;
    minim22=j;
    minim2=maxim[j];
    for(k=1;k<=n;k++)
        {if(v[k]==v[i]&&maxim[k]<=minim1)
        {minim11=k;
          minim1=maxim[k];
        }


        if(v[k]==v[j]&&maxim[k]<=minim2)
        {minim22=k;
        minim2=maxim[k];

        }
        }
    c++;
  xx[c]=minim11;
  yy[c]=minim22;
a[minim22][minim11]=a[minim11][minim22]=1;
maxim[minim11]++;
maxim[minim22]++;
for(k=1;k<=n;k++)
    if(v[k]==q)
    v[k]=v[i];
}

}

for(i=1;i<=n;i++)
if(maxim[i]>qq)
    qq=maxim[i];
g<<qq<<'\n';
g<<c<<'\n';
for(i=1;i<=c;i++)
    g<<xx[i]<<" "<<yy[i]<<'\n';

}