{$APPTYPE CONSOLE}
{$I-,S-,Q-,R-,D-,L-,Y-,P-}
const maxq=200000;
      maxn=100;
      maxm=3000;
      inf=1000000000;

var px,py,aa,d:array[1..maxn,1..maxn]of longint;
    outx,outy,qx,qy:array[1..maxq]of longint;
    next,first,v:array[1..maxm]of longint;
    c,k:longint;

    n,m,a1,b1,a2,b2:longint;

function get(a,b,c,d:longint):longint;
var s:longint;
begin
  s:=2;
  if a=c then
    dec(s);
  if b=d then
    dec(s);
  if (a=d)and(b=c) then
    s:=inf;
  get:=s;
end;

procedure run;
var na,nb,s,i,j,now,all,a,b:longint;
begin
  now:=0;
  all:=1;
  qx[1]:=a1;
  qy[1]:=b1;
  for i:=1 to maxn do
    for j:=1 to maxn do
      d[i,j]:=inf;
  d[a1,b1]:=0;

  while now<all do
    begin
      if d[a2,b2]<inf then
        break;

      inc(now);
      a:=qx[now];
      b:=qy[now];

      i:=first[a];
      while i>0 do
        begin
          j:=first[b];
          while j>0 do
            begin
              if (aa[v[i],v[j]]=1)and(v[i]<>v[j]) then
                begin
                  s:=get(a,b,v[i],v[j]);
                  if d[v[i],v[j]]>d[a,b]+s then
                    begin
                      inc(all);
                      qx[all]:=v[i];
                      qy[all]:=v[j];
                      d[v[i],v[j]]:=d[a,b]+s;
                      px[v[i],v[j]]:=a;
                      py[v[i],v[j]]:=b;
                    end;
                end;
              j:=next[j];
            end;
          i:=next[i];
        end;
    end;


  c:=d[a2,b2];
  a:=a2;
  b:=b2;
  while (a<>a1)or(b<>b1) do
    begin
      inc(k);
      outx[k]:=a;
      outy[k]:=b;
      na:=px[a,b];
      nb:=py[a,b];
      a:=na;
      b:=nb;
    end;
  inc(k);
  outx[k]:=a1;
  outy[k]:=b1;
end;

var i,cnt,x,y:longint;

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

  read(n,cnt,a1,b1,a2,b2);
  fillchar(first,sizeof(first),0);
  fillchar(aa,sizeof(aa),0);
  m:=0;
  for i:=1 to cnt do
    begin
      read(x,y);
      aa[x,y]:=1;
      aa[y,x]:=1;

      inc(m);
      v[m]:=y;
      next[m]:=first[x];
      first[x]:=m;

      inc(m);
      v[m]:=x;
      next[m]:=first[y];
      first[y]:=m;
    end;

  for i:=1 to n do
    begin
      aa[i,i]:=1;
      inc(m);
      v[m]:=i;
      next[m]:=first[i];
      first[i]:=m;
    end;

  run;
  writeln(c,' ',k);
  for i:=k downto 1 do
    writeln(outx[i],' ',outy[i]);


  close(input);
  close(output);
end.