{$apptype console}

program fin;

const
                infile='kingdom.in';
                outfile='kingdom.out';
                maxn=101;

type
                int=longint;
                node=record
                        x,y:int;
                     end;

var
        a               :array [1..maxn,1..maxn] of boolean;
        c               :array [1..maxn,1..maxn] of int;
        d               :array [1..maxn,1..maxn] of node;
        p               :array [1..maxn,1..maxn] of boolean;
        r               :array [1..maxn*maxn] of node;
        n,m,a1,b1,a2,b2 :int;
        can             :boolean;
        k               :int;

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

function con(x,y,p,r:int):int;
var
        sum:int;
begin
  sum:=0;
  if x<>p then inc(sum);
  if y<>r then inc(sum);
  con:=sum;
end;

procedure solve;
var
        i,j,x,y,min,t,q:int;
begin
  for i:=1 to n do for j:=1 to n do c[i,j]:=maxint;
  fillchar(d,sizeof(d),0);
  fillchar(p,sizeof(p),false);
  c[a1,b1]:=0;
  can:=true;
  while can do begin
    can:=false;
    min:=maxint;
    for i:=1 to n do
     for j:=1 to n do
      if (c[i,j]<min) and (not p[i,j]) then begin
        min:=c[i,j];
        can:=true;
        x:=i;
        y:=j;
       end;
    p[x,y]:=true;
    for i:=1 to n do
     for j:=1 to n do
      if(i<>j)and(a[i,j])and(a[x,i])and(a[y,j])then
       if(x<>j)or(y<>i)then 
       if c[i,j]>c[x,y]+con(x,y,i,j) then begin
         c[i,j]:=c[x,y]+con(x,y,i,j);
         d[i,j].x:=x;
         d[i,j].y:=y;
        end;
   end;
  k:=1;
  r[k].x:=a2;
  r[k].y:=b2;
  i:=a2;
  j:=b2;
  repeat
    t:=i;
    q:=j;
    i:=d[t,q].x;
    j:=d[t,q].y;
    inc(k);
    r[k].x:=i;
    r[k].y:=j;
  until(i=a1)and(j=b1);
end;

procedure print;
var
        i:int;
begin
  assign(output,outfile);
  rewrite(output);
  writeln(c[a2,b2],' ',k);
  for i:=k downto 1 do writeln(r[i].x,' ',r[i].y);
  close(output);
end;

begin
  load;
  solve;
  print;
end.
