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

type
  int = longint;

var
  que : array [0..maxq] of array [1..2] of int;{byte}
  pred : array [0..maxq] of int;
  g : array [0..maxn, 0..maxn] of boolean;
  d, a : array [0..maxn, 0..maxn] of int;
  ee, was : array [0..maxn, 0..maxn] of boolean;
  u : array [0..maxn] of boolean;
  n, m, cur1, cur2, a1, b1, a2, b2, ql, qr, p1, p2, a3, b3 : int;
  k, ind, i, j, ii, jj : 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, dd : int);
begin
  inc(qr);
  que[qr mod maxq][1] := cur1;
  que[qr mod maxq][2] := cur2;
  d[cur1, cur2] := dd;
  was[cur1, cur2] := true;
  pred[qr] := ql;
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
  dd : int;
begin
  dd := 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(not was[i, j])and(i <> j)then begin

          if(i = cur2)and(j = cur1)then continue;

          addque(i, j, dd + 1);
          if(i = a2)and(j = b2)then begin
            a3 := i;
            b3 := j;
            ind := qr;
            exit;
          end;
        end;
      end;
    end;
    extractque(cur1, cur2);
    dd := d[cur1, cur2];
  until ql > qr;
end;

procedure rec(ind : int);
begin
  if ind = 0 then begin
    writeln(a1, ' ', b1)
  end else begin
    rec(pred[ind]);
    writeln(que[ind][1], ' ', que[ind][2]);
  end;
end;

procedure add2(a, b : int);
begin
  ee[a, b] := true;
  ee[b, a] := true;
end;

procedure rec1(al, bl, ind : int);
begin
  if ind = 0 then begin
    add2(al, a1);
    add2(bl, b1);
  end else begin
    rec1(que[ind][1], que[ind][2], pred[ind]);
    add2(al, que[ind][1]);
    add2(bl, que[ind][2]);
  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);

  ql := 0;
  qr := 0;
  cur1 := a1;
  cur2 := b1;

  solve;

  assign(output, ouf);
  rewrite(output);
  rec1(a3, b3, ind);
  for i := 1 to n - 1 do for j := i + 1 to n do if ee[i, j] then inc(k);
  writeln(d[a3, b3] + 1, ' ', k);
  rec(ind);
  close(output);
end.
