var
  mas: array [1..100, 1..100] of boolean;
  r: array [1..100, 1..100] of Integer;
  f: array [1..100, 1..100] of byte;
  path: array [1..10000, 1..2] of integer;
  pair, w, mina, minb, t1, t2, n, m, a1, a2, b1, b2: integer;
  i, j: integer;
  fl: boolean;

procedure cur(var a, b: integer);
var k, l, min: integer;
begin
  min := MaxInt;
  for k := 1 to n do
    for l := 1 to n do
      if (f[k, l] = 1) and (r[k, l] < min) then
      begin
        min := r[k, l];
        a := k;
        b := l;
      end;
end;

function is_way(a, b, c, d: byte): integer;
begin
  if not (mas[a, c] and mas[b, d] and mas[c, d]) then
    result := -1
  else
  if ((a = d) and (b = c)) or (c = d) then
    result := -1
  else
  begin
    if (a = c) and (b = d) then
      result := 0
    else
      if (a = c) or (b = d) then
        result := 1
      else
        result := 2;
  end;
end;

begin
  fillchar(mas, sizeof(mas), false);
  assign(input, 'kingdom.in');
  assign(output, 'kingdom.out');
  reset(input);
  rewrite(output);
  readln(n, m, a1, b1, a2, b2);
  for i := 1 to 100 do
    mas[i, i] := true;
  for i := 1 to m do
  begin
    readln(t1, t2);
    mas[t1, t2] := true;
    mas[t2, t1] := true;
  end;

  for i := 1 to n do
    for j := 1 to n do
    begin
      r[i, j] := MAXINT;
      f[i, j] := 0;
    end;
  r[a1, b1] := 0;
  f[a1, b1] := 1;
  while f[a2, b2] <> 2 do
  begin
    cur(mina, minb);
    if (mina = a2) and (minb = b2) then
      break;
    for i := 1 to n do
      for j := 1 to n do
      begin
        w := is_way(mina, minb, i, j);
        if (f[i, j] <> 2) and (w > 0) then
        begin
          if r[i, j] > r[mina, minb] + w then
            r[i, j] := r[mina, minb] + w;
          f[i, j] := 1;
        end;
      end;
    f[mina, minb] := 2;
  end;

  write(r[a2, b2]);
  pair := 1;
  path[1, 1] := a2;
  path[1, 2] := b2;
  mina := a2; minb := b2;
  while (mina <> a1) or (minb <> b1) do
  begin
    for i := 1 to n do
    begin
      fl := false;
      for j := 1 to n do
      begin
        w := is_way(mina, minb, i, j);
        if (f[i, j] = 2) and (r[i, j] + w = r[mina, minb]) then
        begin
          inc(pair);
          path[pair, 1] := i;
          path[pair, 2] := j;
          mina := i; minb := j;
          fl := true;
          break;
        end;
      end;
      if fl then
       break;
    end;
  end;

  inc(pair);
  path[pair, 1] := a1;
  path[pair, 2] := b1;

  writeln(' ', pair);
  for i := pair-1 downto 1 do
    writeln(path[i, 1], ' ', path[i, 2]);

  close(input);
  close(output);
end.
