program k;

{$APPTYPE CONSOLE}

const fname = 'kingdom';
      ifile = fname + '.in';
      ofile = fname + '.out';
      MAXN = 200;
      MAXM = 3000;

var n,m,a1,b1,a2,b2: longint;
    mas: array[1..MAXN,1..MAXN]of byte;
    o,p: array[1..MAXM,1..2]of longint;
    f: array[1..MAXN,1..MAXN]of byte;
    mmm,mm: array[1..MAXN,1..MAXN]of longint;
    pr: array[1..MAXN,1..MAXN,1..2]of longint;

procedure load();
var k,kk,ll: longint;
begin
  read(n,m,a1,b1,a2,b2);
  for k:=1 to m do begin
    read(kk,ll);
    p[k,1]:=kk;
    p[k,2]:=ll;
    mas[kk,ll]:=1;
    mas[ll,kk]:=1;
  end;
  for k:=1 to n do
    mas[k,k]:=1;
end;

procedure solve();
var numo,k,l,min,min1,min2,kk,ll:longint;
begin
  f[a1,b1]:=1;
  mm[a1,b1]:=1;
  while true do begin
    min:=100000; min1:=0; min2:=0;
    for k:=1 to m do begin
      kk:=p[k,1];
      ll:=p[k,2];
      if (f[kk,ll]=1)and(min>mm[kk,ll]) then begin
        min:=mm[kk,ll];
        min1:=kk;
        min2:=ll;
      end;

      ll:=p[k,1];
      kk:=p[k,2];
      if (f[kk,ll]=1)and(min>mm[kk,ll]) then begin
        min:=mm[kk,ll];
        min1:=kk;
        min2:=ll;
      end;
    end;

    if (min1=a2)and(min2=b2) then 
      break;
    f[min1,min2]:=2;
    for k:=1 to m do begin
      kk:=p[k,1];
      ll:=p[k,2];
      if ((kk<>min2)or(ll<>min1))and(mas[min1,kk]=1)and(mas[min2,ll]=1) then begin
        l:=min;
        if kk<>min1 then inc(l);
        if ll<>min2 then inc(l);
        if (f[kk,ll]=0)or(mm[kk,ll]>l) then begin
          f[kk,ll]:=1;
          mm[kk,ll]:=l;
          mmm[kk,ll]:=mmm[min1,min2]+1;
          pr[kk,ll,1]:=min1;
          pr[kk,ll,2]:=min2;
        end;
      end;

      ll:=p[k,1];
      kk:=p[k,2];
      if ((kk<>min2)or(ll<>min1))and(mas[min1,kk]=1)and(mas[min2,ll]=1) then begin
        l:=min;
        if kk<>min1 then inc(l);
        if ll<>min2 then inc(l);
        if (f[kk,ll]=0)or(mm[kk,ll]>l) then begin
          f[kk,ll]:=1;
          mm[kk,ll]:=l;
          mmm[kk,ll]:=mmm[min1,min2]+1;
          pr[kk,ll,1]:=min1;
          pr[kk,ll,2]:=min2;
        end;
      end;
    end;
  end;

  writeln(mm[a2,b2]-1,' ',mmm[a2,b2]+1);
  numo:=0;
  while (a2<>a1)or(b1<>b2) do begin
    inc(numo);
    o[numo,1]:=a2;
    o[numo,2]:=b2;
    k:=pr[a2,b2,1];
    b2:=pr[a2,b2,2];
    a2:=k;
  end;
  writeln(a1,' ',b1);
  for k:=numo downto 1 do
    writeln(o[k,1],' ',o[k,2]);
end;

procedure save();
begin

end;

begin
  assign(input,ifile);
  reset(input);
  assign(output,ofile);
  rewrite(output);
  load;
  solve;
  save;
end.
 