{$R-,Q-,O+}
const
  MAXM = 3000;
  MAXN = 129;
  oo = MAXINT div 2;
var
  a: array[0..MAXM, 0..MAXM] of integer;
  g: array[0..MAXN, 0..MAXN] of boolean;
  e: array[0..MAXM, 1..2] of integer;
  ans, d, pi: array[0..MAXM] of integer;
  inq: array[0..MAXM] of boolean;
  cnt, n, min, m, t, s, a1, b1, a2, b2, i, j: integer;
begin
  reset(input, 'kingdom.in'); rewrite(output, 'kingdom.out');

  read(n, m, a1, b1, a2, b2);

  i := 0; m := 2*m;
  while i <= m-2 do begin
    inc(i);
    read(e[i][1], e[i][2]);

    inc(i);
    e[i][1] := e[i-1][2]; e[i][2] := e[i-1][1];

    g[e[i][1], e[i][2]] := true;
    g[e[i][2], e[i][1]] := true;
  end;

  for i := 1 to m do
    for j := 1 to m do
      if (e[i][1] = e[j][1]) and g[e[i][2], e[j][2]] then
        a[i][j] := 1
      else
      if (e[i][2] = e[j][2]) and g[e[i][1], e[j][1]] then
        a[i][j] := 1
      else
      if g[e[i][1], e[j][1]] and g[e[i][2], e[j][2]] and (not (((e[i][1]=e[i][2]) and (e[j][1]=e[j][2]))
       or ((e[i][1]=e[j][2]) and (e[j][1]=e[i][2])))) then
        a[i][j] := 2
      else a[i][j] := oo;

  s := 0;
  for i := 1 to m do
    if (e[i][1] = a1) and (e[i][2] = b1) then begin
      s := i;
      break;
    end;


  for i := 1 to m do d[i] := oo;
  d[s] := 0; inq[s] := true;

  while true do begin
    min := -1;
    for i := 1 to m do
      if inq[i] and ((min = -1) or (d[i] < d[min])) then
        min := i;

    if min = -1 then break;

    inq[min] := false;
    for i := 1 to m do
      if (a[min, i] < oo) and (d[i] > d[min] + a[min, i]) then begin
        inq[i] := true;
        pi[i] := min;
        d[i] := d[min] + a[min, i];
      end;
  end;

  t := 0;
  for i := 1 to m do
    if (e[i][1] = a2) and (e[i][2] = b2) then begin
      t := i;
      break;
    end;

  write(d[t]);

  cnt := 0;
  while (e[t][1] <> a1) or (e[t][2] <> b1) do begin
    inc(cnt);
    ans[cnt] := t;
    t := pi[t];
  end;
  writeln(' ', cnt+1);

  writeln(a1, ' ', b1);
  for i := cnt downto 1 do writeln(e[ans[i]][1], ' ', e[ans[i]][2]);
end.

