{$I-,Q-,R-,S-,D-,L-,O+}
{$I+,Q+,R+,S+,D+,L+,O-}
program K2;
{$APPTYPE CONSOLE}
const
  inf = 'kingdom.in';
  ouf = 'kingdom.out';
  maxn = 112;
  maxq = maxn * maxn * 10;

type
  int = longint;

var
  que : array [0..maxq] of array [1..2] of int;{byte}
  g : array [0..maxn, 0..maxn] of boolean;
  pr : array [0..maxn, 0..maxn] of array [1..2] of int;
  a, dm : array [0..maxn, 0..maxn] of int;
  n, m, cur1, cur2, a1, b1, a2, b2, ql, qr, p1, p2, a3, b3 : int;
  k, c, ind, i, j : int;

procedure add(e1, e2 : int);
begin
  g[e1, e2] := true;
  inc(a[e1, 0]);
  a[e1, a[e1, 0]] := e2;
end;

procedure addque(cur1, cur2 : int);
begin
  inc(qr);
  que[qr mod maxq][1] := cur1;
  que[qr mod maxq][2] := cur2;
end;

procedure extractque(var cur1, cur2 : int);
begin
  inc(ql);
  cur1 := que[ql mod maxq][1];
  cur2 := que[ql mod maxq][2];
end;

procedure solve;
var
  i, j, tmp, ii, jj, dd : int;
begin
  ql := 0;
  qr := 0;
  cur1 := a1;
  cur2 := b1;
  dd := 0;
  for i := 1 to n do for j := 1 to n do dm[i, j] := maxint shr 1;
  dm[a1, b1] := 0;
  repeat
    for ii := 1 to a[cur1, 0] do begin
      i := a[cur1, ii];

      for jj := 1 to a[cur2, 0] do begin
        j := a[cur2, jj];
        if(ii > 1)then tmp := 1 else tmp := 0;
        if(jj > 1)then inc(tmp);

        if(i <> j)and(g[i, j])then begin

          if((i = cur2)and(j = cur1))then continue;
          if(dm[i, j] <= dd + tmp)then continue;

          dm[i, j] := dd + tmp;

          pr[i, j][1] := cur1;
          pr[i, j][2] := cur2;

          addque(i, j);
        end;
      end;
    end;
    extractque(cur1, cur2);
    dd := dm[cur1, cur2];
  until ql > qr;
end;

procedure rec(a, b : int);
begin
  if(a = a1)and(b = b1)then begin
    writeln(a, ' ', b)
  end else begin
    rec(pr[a, b][1], pr[a, b][2]);
    writeln(a, ' ', b);
  end;
end;

procedure rec1(a, b : int);
begin
  if(a = a1)and(b = b1)then begin
    inc(k);
    exit;
  end else begin
    inc(k);
    rec1(pr[a, b][1], pr[a, b][2]);
    if a <> pr[a, b][1] then inc(c);
    if b <> pr[a, b][2] then inc(c);
  end;
end;

begin
  assign(input, inf);
  reset(input);
  read(n, m, a1, b1, a2, b2);

  for i := 1 to n do add(i, i);

  for i := 1 to m do begin
    read(p1, p2);
    add(p1, p2);
    add(p2, p1);
  end;

  close(input);

  solve;

  assign(output, ouf);
  rewrite(output);

  rec1(a2, b2);

  writeln(c, ' ', k);
  rec(a2, b2);
  close(output);
end.
