const maxm=100000;
      maxn=101;
type  MType=record
                  x,y           : LongInt;
            end;
var     i,j,k,l,m,n             : LongInt;
        x1,y1,x2,y2             : LongInt;
        A                       : Array[1..100,1..100] of LongInt;
        B                       : Array[1..maxn,1..maxn] of Mtype;
        T                       : Array[1..100,1..100] of Byte;
        Q                       : Array[1..maxm] of MType;
        x                       : LongInt;
        zero                    : MType;
        W                       : Array[1..maxm] of MType;
        f                       : MType;

function same(x1,y1,x2,y2: LongInt): boolean;
begin
 same:=((x1=x2)and(y1=y2))or
       ((x1=y2)and(y1=x2));
end;


BEGIN
 fillchar(zero,sizeof(zero),0);
 Assign(Input,'kingdom.in');
 Assign(Output,'kingdom.out');
 Rewrite(Output);
 Reset(Input);
  Read(N,M,x1,y1,x2,y2);
  for i:=1 to N do
   t[i,i]:=1;
  For i:=1 to M do
  begin
   read(k,l);
   t[k,l]:=1;
   t[l,k]:=1;
  end;
  fillchar(a,sizeof(a),0);

  l:=0; a[x1,y1]:=1; m:=1;
  q[1].x:=x1; q[1].y:=y1;
  while true do
  begin
   inc(L);
   For i:=1 to N do
    if t[q[l].x,i]=1 then
     For j:=1 to N do
      if t[q[l].y,j]=1 then
       if i<>j then
       if not(same(i,j,q[l].x,q[l].y)) then
       if t[i,j]=1 then
       begin
        If (I=q[l].x)or(j=q[l].y) then x:=1 else x:=2;
        if (a[i,j]=0)or(a[i,j]>a[q[l].x,q[l].y]+x) then
        begin
         a[i,j]:=a[q[l].x,q[l].y]+x;
         inc(m);
         q[m].x:=i;
         q[m].y:=j;
         b[i,j]:=q[l];
        end;
       end;
   If L=M then break;
  end;


  l:=0; f.x:=x2; f.y:=y2;
  while (f.x>0)and(f.y>0) do
  begin
   inc(L);
   w[l]:=f;
   f:=b[f.x,f.y];
  end;

  writeln(a[x2,y2]-1,' ',l);
  for i:=L downto 1 do
   writeln(w[i].x,' ',w[i].y);


 Close(INput);
 Close(Output);
END.