program xx;
const inp='kingdom.in';
     outp='kingdom.out';
type ika=record
          an,a,b:longint;
         end;
     ii=record
         a,b:longint;
        end;
var a:array [0..101,0..101] of boolean;
    b:array [0..101,0..101] of longint;
    ans:array [0..101,0..101] of ika;
    tal:array [0..2000000] of ii;
    aa,bb,k,p,q,w,e,t,n,m,a1,b1,a2,b2:longint;

begin
 assign(input,inp); reset(input);
 assign(output,outp); rewrite(output);
 read(n,m,a1,b1,a2,b2);
 fillchar(a,sizeof(a),false);
 fillchar(b,sizeof(b),0);
 for k:=1 to m do
  begin
   read(q,w);
   a[q,w]:=true; a[w,q]:=true;
   inc(b[q,0]); b[q,b[q,0]]:=w;
   inc(b[w,0]); b[w,b[w,0]]:=q;
  end;
 for k:=1 to n do
 for p:=1 to n do ans[k,p].an:=50000;
 ans[a1,b1].an:=0;
 tal[1].a:=a1; tal[1].b:=b1;
 q:=1; w:=1;
 while true do
  begin
   e:=w;
   for k:=q to w do
    begin
     aa:=tal[k].a;
     bb:=tal[k].b;
     for p:=1 to b[aa,0] do
     begin
      if (ans[b[aa,p],bb].an>ans[aa,bb].an+1)and(b[aa,p]<>bb)and(a[b[aa,p],bb])
         then begin
               inc(e);
               tal[e].a:=b[aa,p];
               tal[e].b:=bb;
               ans[b[aa,p],bb].an:=ans[aa,bb].an+1;
               ans[b[aa,p],bb].a:=aa;
               ans[b[aa,p],bb].b:=bb;
              end;
      for t:=1 to b[bb,0] do
       begin
        if (ans[aa,b[bb,t]].an>ans[aa,bb].an+1)and(b[bb,t]<>aa)and(a[aa,b[bb,t]])
         then begin
               inc(e);
               tal[e].a:=aa;
               tal[e].b:=b[bb,t];
               ans[aa,b[bb,t]].an:=ans[aa,bb].an+1;
               ans[aa,b[bb,t]].a:=aa;
               ans[aa,b[bb,t]].b:=bb;
              end;
         if (ans[b[aa,p],b[bb,t]].an>ans[aa,bb].an+2)and((b[bb,t]<>aa)or(b[aa,p]<>bb))
            and(a[b[aa,p],b[bb,t]])
            then begin
                  ans[b[aa,p],b[bb,t]].an:=ans[aa,bb].an+2;
                  ans[b[aa,p],b[bb,t]].a:=aa;
                  ans[b[aa,p],b[bb,t]].b:=bb;
                  inc(e);
                  tal[e].a:=b[aa,p];
                  tal[e].b:=b[bb,t];
                 end;
       end;
     end;
    end;
    if ans[a2,b2].an<50000 then break;
   if e=w then break;
   q:=w+1;
   w:=e;
  end;
 q:=0; w:=ans[a2,b2].an;
 e:=a2; t:=b2;
 while true do
  begin
   inc(q); tal[q].a:=e; tal[q].b:=t;
   if ans[e,t].an=0 then break;
   a2:=ans[e,t].a;
   b2:=ans[e,t].b;
   e:=a2; t:=b2;
  end;
 writeln(w,' ',q);
 for k:=q downto 1 do writeln(tal[k].a,' ',tal[k].b);
 close(input); close(output);
end.
