{$apptype console}

program kingdom;

const
                infile='kingdom.in';
                outfile='kingdom.out';
                maxn=100;
                maxm=1000;

type
                int=integer;
                node=record
                       q:int;
                       x,y,t:byte;
                     end;
                po=record
                     x,y:byte;
                   end;
var
                a       :array [1..maxm,1..maxn,1..maxn] of boolean;
                c       :array [1..maxn,1..maxn] of byte;
                p       :array [1..maxn,1..maxn] of boolean;
                b       :array [1..maxn] of byte;
                d       :array [1..maxm*maxn*maxn] of node;
                re      :array [1..maxm*maxn] of po;
                k,q     :int;
                n,m     :int;
                a1,b1,a2,b2:int;
                cnt,rees  :int;
                i,j     :int;
                res     :int;

procedure load;
var
        i,x,y:int;
begin
  assign(input,infile);
  reset(input);
  read(n,m,a1,b1,a2,b2);
  fillchar(b,sizeof(b),0);
  fillchar(a,sizeof(a),true);
  fillchar(p,sizeof(p),false);
  for i:=1 to m do begin
    read(x,y);
    if not p[x,y] then begin
      p[x,y]:=true;
      p[y,x]:=true;
      inc(b[x]);
      inc(b[y]);
      c[x,b[x]]:=y;
      c[y,b[y]]:=x;
     end;
   end;
  for i:=1 to n do begin
    inc(b[i]);
    c[i,b[i]]:=i;
   end;
  close(input);
end;

function check(p,r,x,y,t:int):boolean;
begin
  check:=true;
  if (x=r)and(y=p)then check:=false;
  if not a[t,p,r] then check:=false;
end;

procedure solve;
begin
  k:=1;
  q:=0;
  d[1].x:=a1;
  d[1].y:=b1;
  d[1].q:=0;
  a[1,a1,b1]:=false;
  d[1].t:=1;
  while q<k do begin
    inc(q);
    for i:=1 to b[d[q].x] do
     for j:=1 to b[d[q].y] do
      if(c[d[q].x,i]<>c[d[q].y,j])and(p[c[d[q].x,i],c[d[q].y,j]])and(check(c[d[q].x,i],c[d[q].y,j],d[q].x,d[q].y,d[q].t+1))then begin
        inc(k);
        d[k].x:=c[d[q].x,i];
        d[k].y:=c[d[q].y,j];
        d[k].t:=d[q].t+1;
        d[k].q:=q;
        a[d[k].t,d[k].x,d[k].y]:=true;
        if(d[k].x=a2)and(d[k].y=b2)then begin
          cnt:=k;
          exit;
         end;
       end;
   end;
end;

procedure print;
var
        i,j:int;
begin
  assign(output,outfile);
  rewrite(output);
  res:=0;
  i:=cnt;
  j:=0;
  repeat
    inc(res);
    re[res].x:=d[i].x;
    re[res].y:=d[i].y;
    if res>1 then begin
      if re[res].x<>re[res-1].x then inc(j);
      if re[res].y<>re[res-1].y then inc(j);
     end;
    i:=d[i].q;
  until i=0;
  writeln(j,' ',d[cnt].t);
  for j:=res downto 1 do writeln(re[j].x,' ',re[j].y);
  close(output);
end;

begin
  load;
  solve;
  print;
end.
