var     w:array of array of 0..1;
        v:array[0..100000]of longint;
        q,d,l:array[0..100000]of longint;
        n,i,j,m,x,y,max,maxi,u,p:longint;

begin

assign(input,'mesaj4.in');
assign(output,'mesaj4.out');
reset(input);
rewrite(output);

readln(n,m);
setlength(w,n+1,n+1);

for i:=1 to m do
begin
        readln(x,y);
        w[x,y]:=1;
        w[y,x]:=1;
        inc(d[x]);
        inc(d[y]);
end;


for i:=1 to n do
if d[i]>max then
begin
        max:=d[i];
        maxi:=i;
end;

u:=1;
q[p+1]:=maxi;
repeat
inc(p);
for i:=1 to n do
begin
        if (w[q[p],i]=1)and((l[q[p]]+1<l[i])or(l[i]=0))and(q[p]<>i) then
        begin
                inc(u);
                l[i]:=l[q[p]]+1;
                q[u]:=i;
                v[i]:=q[p];
        end;
end;


until p>=i;

writeln(p*2);

for i:=1 to p do
writeln(i,' ',v[q[i]]);

for i:=1 to p do
writeln(v[q[i]],' ',i);

close(output);
end.