{$APPTYPE CONSOLE}
{$O-,R+,Q+}
uses
  Sysutils, Math;
const
  inf = 1000000000;
  eps = 1e-9;
  base = 10;
type
  int = longint;
  bool = boolean;
  real = extended;
var
  cv, mm, nn, i, j, k, n, m: int;
  a: array[1..100, 1..100] of int;
  q: array[1..100000] of int;
  u, v, h, t: int;
  a1, b1, a2, b2: int;
  e: array[1..2000, 1..2] of int;
  b: array[1..2000, 1..2000] of int;
  d, pi: array[1..2000] of int;

procedure writePath(cv: int);
begin
  if cv = -1 then exit;
  writePath(pi[cv]);
  writeln(e[cv][1], ' ', e[cv][2]);
end;

begin
  assign(input, 'kingdom.in');
  reset(input);
  assign(output, 'kingdom.out');
  rewrite(output);

  read(n, m);
  read(a1, b1, a2, b2);
  for i := 1 to m do
  begin
    read(u, v);
    e[i][1] := u;
    e[i][2] := v;
    e[m + i][1] := v;
    e[m + i][2] := u;
    a[u][v] := i;
    a[v][u] := m + i;
  end;

  m := 2 * m;

  for i := 1 to m do
  begin
    u := e[i][1];
    v := e[i][2];
    for j := 1 to n do
    begin
      if (a[v][j] <> 0) and (a[u][j] <> 0) then
      begin
        b[i][a[u][j]] := 1;
      end;
    end;
    for j := 1 to n do
    begin
      if (a[v][j] <> 0) and (a[u][j] <> 0) then
      begin
        b[i][a[j][v]] := 1;
      end;
    end;
  end;
  for i := 1 to m do
  begin
    d[i] := inf;
  end;
  nn := a[a1][b1];
  
  h := 1;
  t := 2;
  q[1] := nn;
  d[nn] := 0;
  pi[nn] := -1;
  while h < t do
  begin
    u := q[h];
    inc(h);
    for i := 1 to m do
    begin
      if (b[u][i] = 1) and (d[i] = inf) then
      begin
        d[i] := d[u] + 1;
        q[t] := i;
        inc(t);
        pi[i] := u;
      end;
    end;
  end;
  mm := a[a2][b2];

  writeln(d[mm], ' ', d[mm] + 1);
  writePath(mm);
  close(input);
  close(output);
end.
//Leafy tops of root vegetables strike back...