type ref=^inr;
     inr=record
     x:byte;
     next:ref;
     end;
var f,g:text;
a:array[1..255,1..255]of 0..1;
c,t,d:array[1..500]of byte;
viz:array[1..255]of boolean;
cont,ne,muchii:array[1..255]of byte;
ok,gasit:boolean;
pr,q:ref;
i_c,sf_c,k,p,n,m,i,i1,i2,mc,j,x,max,j2,nod:longint;
begin
assign(f,'strazi.in');reset(f);readln(f,n,m);
for i:=1 to m do begin
 readln(f,i1,i2);
 a[i1,i2]:=1;
 cont[i1]:=cont[i1]+1;
 end;
close(f);
i_c:=1;
sf_c:=1;
c[1]:=1;
viz[1]:=true;
k:=1;
d[1]:=1;
t[1]:=0;
while i_c<=sf_C do begin
 ok:=false;gasit:=false;
 for i:=1 to n do if (a[c[i_c],i]=1)and not(viz[i]) and not(ok) then begin
   ok:=true;
   gasit:=true;
   sf_C:=sf_c+1;
   c[sf_c]:=i;
   d[sf_C]:=d[i_c];
   t[sf_c]:=c[i_C];
   viz[i]:=true;
   end else if (a[c[i_c],i]=1)and (not(viz[i])) and ok then begin
    sf_C:=sf_c+1;
    c[sf_c]:=i;
    k:=k+1;
    d[sf_C]:=k;
    t[sf_C]:=c[i_c];
    viz[i]:=true;
    end;
  if not(gasit)and(i_c<sf_C) then begin {stergere}
   i:=c[i_c];
   dec(cont[t[i_c]]);
   i:=t[i_c];
   viz[i_c]:=false;
   c[i_c]:=0;
   while i<>0 do begin
   if (cont[i]=0) then begin
    viz[i]:=false;
    c[i]:=0;
    d[i]:=0;
    dec(cont[t[i]]);
    end else i:=0;
   i:=t[i];
   end;
  end;
 i_c:=i_C+1;
 end;
i_c:=sf_c;
k:=0;
muchii[1]:=c[sf_c]; mc:=1;
{for i:=1 to n do if not(viz[i]) then begin
 gasit:=false;
 for j:=1 to n do if (a[i,j]<>0)and not(viz[j])and (a[j,i]<>0) then gasit:=true;

 if gasit then begin
   k:=k+1;
   ne[k]:=i;
   end else begin
 mc:=mc+1;
 t[i]:=c[sf_c];
 sf_c:=sf_c+1;
 c[sf_c]:=i;
 muchii[mc]:=i;
 viz[i]:=true;
 end;
end;{if not viz..}
repeat
k:=0;
for i:=1 to n do if not(viz[i]) then begin
 k:=k+1;
 ne[k]:=i;
 end;
for i:=1 to k do begin
 j:=ne[i];x:=0;
 while (j<>0)and not(viz[j]) do begin
  j2:=j;
  j:=t[j];
  x:=x+1;
  end;
 if max<x then begin
   max:=x;
   nod:=j2;
   end;
 end;
if k>0 then begin
max:=0;
mc:=mc+1;
muchii[mc]:=nod;
k:=k-1;
t[nod]:=c[sf_c];
sf_c:=sf_c+1;
c[sf_c]:=nod;
viz[nod]:=true;
i_c:=sf_c;
while i_c<=sf_C do begin
 for i:=1 to n do if not(viz[i]) then if a[c[i_c],i]=1 then begin
   viz[i]:=true;
   k:=k-1;
   sf_c:=sf_C+1;
   c[sf_c]:=i;
   end;
 i_c:=i_c+1;
 end;
end;{if k>0}
until k=0;
{p:=sf_c;
k:=0;
for i:=1 to n do if not(viz[i]) then begin
 k:=k+1;
 sf_c:=sf_C+1;
 c[sf_c]:=i;
 t[sf_c]:=c[i_c];
 i_c:=sf_C;
 end;
}
new(pr);
pr^.x:=c[sf_C];
pr^.next:=nil;
i:=t[c[sf_C]];
while i<>0 do begin
 new(q);
 q^.x:=i;
 q^.next:=pr;
 pr:=q;
 i:=t[i];
 end;
assign(g,'strazi.out');rewrite(g);
writeln(g,mc-1);
for i:=1 to mc-1 do writeln(g,muchii[i],' ',muchii[i+1]);
while pr<>nil do begin
 write(g,pr^.x,' ');
 pr:=pr^.next;
 end;
close(g);
end.