{$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;
  u1, v1, 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;
  cnt, d, pi: array[1..2000] of int;
  min, mini: int;
  w: array[1..2000] of bool;
  
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;
    for j := 1 to m do
    begin
      u1 := e[j][1];
      v1 := e[j][2];
      if (a[u][u1] <> 0) and (a[v][v1] <> 0) and ((u1 <> v) and (v1 <> u)) then
      begin
        b[i][j] := 2;
      end;
    end;
  end;
  for i := 1 to m do
  begin
    d[i] := inf;
    w[i] := false;
  end;
  nn := a[a1][b1];
  
  h := 1;
  t := 2;
  q[1] := nn;
  d[nn] := 0;
  pi[nn] := -1;
  cnt[nn] := 1;
  while true do
  begin
    min := inf;
    mini := -1;
    for i := 1 to m do
    begin
      if (min > d[i]) and (not w[i]) then
      begin
        min := d[i];
        mini := i;
      end;
    end;
    if mini = -1 then break;
    w[mini] := true;
    for i := 1 to m do
    begin
      if b[mini][i] <> 0 then
      begin
        if d[i] > d[mini] + b[mini][i] then
        begin
          d[i] := d[mini] + b[mini][i];
          pi[i] := mini;
          cnt[i] := cnt[mini] + 1;
        end;
      end;
    end;
  end;
  mm := a[a2][b2];

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