program taskk1;
{$APPTYPE CONSOLE}
{ $I+,Q+,R+,O-}
{$I-,Q-,R-,O+}
uses
  SysUtils,Math;
type
  short=smallint;
  long=longint;
  ex=extended;
  bool=boolean;


var
  va,vb:array[1..2000]of short;
  nn,a1,a2,b1,b2,mm:long;
  i,j:long;
  curv,mn,mx:long;
  d,pp,p,v:array[1..2005]of long;
  n,src,dst:long;
  a:array[1..2000,1..2000]of byte;
  p1,p2:long;
  pc:Long;
  aa:array[1..100,1..100]of short;
  c:short;
begin
  assign(input,'kingdom.in'); reset(input);
  assign(output,'kingdom.out'); rewrite(output);

  read(nn,mm,a1,b1,a2,b2);
  fillchar(a,sizeof(a),0);
  fillchar(aa,sizeof(aa),0);

  n:=0;
  src:=0;
  dst:=0;
  for i:=1 to mm do begin
    read(p1,p2);
    inc(n);
    va[n]:=p1;
    vb[n]:=p2;
    if (p1=a1)and(p2=b1) then src:=n;
    if (p1=a2)and(p2=b2) then dst:=n;
    inc(n);
    va[n]:=p2;
    vb[n]:=p1;
    if (p2=a1)and(p1=b1) then src:=n;
    if (p2=a2)and(p1=b2) then dst:=n;
    aa[p1,p2]:=1;
    aa[p2,p1]:=1;
  end;

  for i:=1 to n do
  for j:=i+1 to n do
  if (i<>j) then repeat
    if (va[i]=vb[j])and(vb[i]=va[j]) then break;

    c:=0;
    if (va[i]<>va[j]) then
      if aa[va[i],va[j]]>0 then inc(c) else break;
    if (vb[i]<>vb[j]) then
      if aa[vb[i],vb[j]]>0 then inc(c) else break;
    a[i,j]:=c;
    a[j,i]:=c;

(*    if a[i,j]>0 then
      writeln(va[i],' ',vb[i],' -- ',va[j],' ',vb[j],' = ',a[i,j])*)
  until true;

  curv:=src;
  for i:=1 to n do d[i]:=high(d[i])shr 1;
  d[curv]:=0;
  fillchar(v,sizeof(v),0);
  fillchar(p,sizeof(p),0);
  mX:=d[curv];
  repeat
    v[curv]:=1;
    for i:=1 to n do if (v[i]=0)and(a[curv,i]>0) then begin
      mn:=mx+a[curv,i];
      if mn<d[i] then begin
        d[i]:=mn;
        p[i]:=curv;
      end;
    end;

    curv:=0;
    mx:=high(mx);
    for i:=1 to n do if (v[i]=0)and(d[i]<mx) then begin
      mx:=d[i];
      curv:=i;
    end;
  until (curv=dst)or(curv=0);

  pc:=0;
  i:=curv;
  while (i<>src) do begin
    inc(pc);
    pp[pc]:=i;
    i:=p[i];
  end;
  inc(pc);
  pp[pc]:=src;

  writeln(d[dst],' ',pc);
  for j:=pc downto 1 do begin
    writeln(va[pp[j]],' ',vb[pp[j]]);
  end;


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