const
 maxn=100+5;
 maxm=1000+5;
 maxq=2*maxn*maxn+2;

type
 tpair=array[0..1]of integer;

var
 n,m:integer;
 p1,p2:tpair;
 es1:array[0..maxn-1,0..maxn-1]of boolean;
 ds:array[0..maxn-1]of integer;
 es:array[0..maxn-1,0..maxn-1]of integer;

procedure readin;
 var
  i:integer;
  a,b:integer;
 begin
  fillchar(ds,sizeof(ds),0);
  fillchar(es,sizeof(es),0);
  fillchar(es1,sizeof(es1),0);
  readln(n,m,p1[0],p1[1],p2[0],p2[1]);
  dec(p1[0]); dec(p1[1]); dec(p2[0]); dec(p2[1]);
  for i:=0 to m-1 do begin
   readln(a,b); dec(a); dec(b);
   es[a,ds[a]]:=b; es[b,ds[b]]:=a;
   inc(ds[a]); inc(ds[b]);
   es1[a,b]:=true; es1[b,a]:=true;
  end;
 end;

var
 was:array[0..maxn-1,0..maxn-1,0..1]of boolean;
 prev:array[0..maxn-1,0..maxn-1,0..1]of tpair;
 prevd:array[0..maxn-1,0..maxn-1,0..1]of integer;
 qu:array[0..maxq-1]of tpair;
 qud:array[0..maxq-1]of integer;
 qh,qt:integer;

var
 gp:tpair;
 gd:integer;
 resd:integer;

procedure qget;
 begin
  gp:=qu[qh]; gd:=qud[qh];
  qh:=(qh+1)mod maxq;
 end;

procedure qput(x0,x1:integer; d:integer);
 begin
  if(es1[x0,x1])then d:=0;
  if(was[x0,x1,d])then exit;
  was[x0,x1,d]:=true; prev[x0,x1,d]:=gp; prevd[x0,x1,d]:=gd;
  qu[qt,0]:=x0; qu[qt,1]:=x1; qud[qt]:=d;
  qt:=(qt+1)mod maxq;
 end;

procedure solve;
 var
  i,j:integer;
 begin
  fillchar(was,sizeof(was),0);
  for i:=0 to n-1 do begin
   was[i,i,0]:=true;
   was[i,i,1]:=true;
  end;
  qh:=0; qt:=0;
  qput(p2[0],p2[1],0);
  while(qh<>qt)and(not was[p1[0],p1[1],0])do begin
   qget;
   if(es1[gp[0],gp[1]])then begin
    for i:=0 to ds[gp[0]]-1 do
     qput(es[gp[0],i],gp[1],0);
    for i:=0 to ds[gp[1]]-1 do
     qput(gp[0],es[gp[1],i],1);
   end else begin
    if(gd=0)then begin
     for i:=0 to ds[gp[1]]-1 do
      if(es1[gp[0],es[gp[1],i]])then
       qput(gp[0],es[gp[1],i],0)
    end else begin
     for i:=0 to ds[gp[0]]-1 do
      if(es1[es[gp[0],i],gp[1]])then
       qput(es[gp[0],i],gp[1],0)
    end;
   end;
  end;
 end;

procedure writeout;
 var
  resp,resn:integer;
  cp:tpair;
  cd,pd:integer;
 begin
  resp:=0; resn:=1;
  cp:=p1; cd:=0;
  while(cp[0]<>p2[0])or(cp[1]<>p2[1])do begin
   pd:=cd;
   cd:=prevd[cp[0],cp[1],pd]; cp:=prev[cp[0],cp[1],pd]; inc(resp); inc(resn);
   if(not es1[cp[0],cp[1]])then begin
    pd:=cd;
    cd:=prevd[cp[0],cp[1],pd]; cp:=prev[cp[0],cp[1],pd]; inc(resp);
   end;
  end;
  writeln(resp,' ',resn);
  cp:=p1; cd:=0;
  writeln(cp[0]+1,' ',cp[1]+1);
  while(cp[0]<>p2[0])or(cp[1]<>p2[1])do begin
   pd:=cd;
   cd:=prevd[cp[0],cp[1],pd]; cp:=prev[cp[0],cp[1],pd]; inc(resp); inc(resn);
   if(not es1[cp[0],cp[1]])then begin
    pd:=cd;
    cd:=prevd[cp[0],cp[1],pd]; cp:=prev[cp[0],cp[1],pd]; inc(resp);
   end;
   writeln(cp[0]+1,' ',cp[1]+1);
  end;
 end;

begin
 assign(input,'kingdom.in'); reset(input);
 assign(output,'kingdom.out'); rewrite(output);
 readin;
 solve;
 writeout;
 close(output);
 close(input);
end.
