{$R+,Q+,O-}
{$MINSTACKSIZE $00404000}
{$APPTYPE CONSOLE}
type
  int = longint;

var
  n, m, i, a, b: int;
  ed, were: array[1..100, 1..100] of boolean;
  best: array[1..100, 1..100] of int;
  e, x: array[1..2000, 1..2] of int;
  c, d: array[0..2000, 1..2000] of byte;
  prp, prd: array[0..2000, 1..2000] of int;
  len: array[0..2000] of int;
  dis, cur: int;
  a1, a2, b1, b2, d1: int;

begin
  assign(input, 'kingdom.in');
  assign(output, 'kingdom.out');
  reset(input);
  rewrite(output);
  read(n, m);
  read(a1, b1);
  read(a2, b2);
  for i := 1 to m do
  begin
    read(a,b);
    e[2 * i - 1, 1] := a;
    e[2 * i - 1, 2] := b;
    e[2 * i, 2] := a;
    e[2 * i, 1] := b;
    ed[a, b] := true;
    ed[b, a] := true;
  end;
  for i := 1 to n do
  begin
    ed[i, i] := true;
  end;
  best[a1, b1] := 1;
  len[0] := 1;
  c[0, 1] := a1;
  d[0, 1] := b1;
  dis := 0;
  cur := 0;
  repeat
    inc(cur);
    if (cur > len[dis]) then
    begin
      inc(dis);
      cur := 1;
    end;
    if (c[dis, cur] = a2) and (d[dis, cur] = b2) then
      break;
    if were[c[dis,cur], d[dis,cur]] then
      continue;
    were[c[dis,cur], d[dis,cur]] := true;
    for i := 1 to 2 * m do
    begin
      if (ed[c[dis,cur], e[i, 1]]) and (ed[d[dis,cur], e[i, 2]]) then
      begin
        if ((e[i, 1] = d[dis,cur]) and (e[i, 2] = c[dis,cur])) or
           ((e[i, 1] = c[dis,cur]) and (e[i, 2] = d[dis,cur])) then
          continue;
        d1 := dis;
        if (e[i, 1] <> c[dis,cur]) then
          inc(d1);
        if (e[i, 2] <> d[dis,cur]) then
          inc(d1);
        if (best[e[i, 1], e[i, 2]] = 0) or (best[e[i, 1], e[i, 2]] + 1 > d1) then
        begin
          best[e[i, 1], e[i, 2]] := d1 + 1;
          inc(len[d1]);
          c[d1, len[d1]] := e[i, 1];
          d[d1, len[d1]] := e[i, 2];
          prd[d1, len[d1]] := dis;
          prp[d1, len[d1]] := cur;
        end;
      end;
    end;
  until false;
  write(dis, ' ');
  i := 0;
  repeat
    inc(i);
    x[i,1] := c[dis, cur];
    x[i,2] := d[dis, cur];
    a := prd[dis, cur];
    cur := prp[dis, cur];
    dis := a;
  until (cur = 0);
  writeln(i);
  while (i > 0) do
  begin
    writeln(x[i, 1], ' ', x[i, 2]);
  end;
end.

