{$A+,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q-,R-,S-,T-,U-,V+,W-,X+,Y+,Z1}

const
  cinfile = 'kingdom.in';
  coutfile = 'kingdom.out';

  nmax = 222;
  mmax = 2222;

  inf = maxlongint shr 1;
  eps = 1e-8;

type
  int = longint;
  real = extended;
  float = extended;

  rebro = record
            x, y : int;
          end;

var
  n, k, m : int;
  ans : int;

  sx, sy : int;
  fx, fy : int;
  s, f : int;

  r : array [1..mmax] of rebro;

  g : array [1..nmax, 1..nmax] of boolean;

  p, d : array [1..mmax] of int;
  u : array [1..mmax] of boolean;

procedure outit(c : int);
begin
  if c = 0 then
  begin
    writeln(ans);
    exit;
  end;
  inc(ans);
  outit(p[c]);
  writeln(r[c].x, ' ', r[c].y);
end;

procedure outdata;
var
  i, j : int;
begin
  write(d[f],' ');
  ans:= 0;
  outit(f);
end;

procedure solve;
var
  i, j : int;
  min, c : int;
begin
  for i:= 1 to mmax do d[i]:= inf;
  d[s]:= 0;
  fillchar(u, sizeof(u), 0);
  fillchar(p, sizeof(p), 0);
  while true do
  begin
    c:= 0;
    min:= inf;
    for i:= 1 to m do
      if not u[i] and (min > d[i]) then
      begin
        min:= d[i];
        c:= i;
      end;
    if c = 0 then break;
    u[c]:= true;
    for i:= 1 to m do
      if not u[i] and ((r[i].x <> r[c].y) or (r[i].y <> r[c].x)) then
      begin
        if (r[i].x = r[c].x) and g[r[c].y, r[i].y] then
          if d[i] > d[c] + 1 then
          begin
            d[i]:= d[c] + 1;
            p[i]:= c;
          end;
        if (r[i].y = r[c].y) and g[r[c].x, r[i].x] then
          if d[i] > d[c] + 1 then
          begin
            d[i]:= d[c] + 1;
            p[i]:= c;
          end;
        if g[r[c].y, r[i].y] and g[r[c].x, r[i].x] then
          if d[i] > d[c] + 2 then
          begin
            d[i]:= d[c] + 2;
            p[i]:= c;
          end;
      end;
  end;

end;

procedure readdata;
var
  i, j : int;
  x, y : int;
begin
  read(n, m);
  read(sx, sy);
  read(fx, fy);
  fillchar(g, sizeof(g), 0);
  for i:= 1 to m do
  begin
    read(x, y);
    g[x, y]:= true;
    g[y, x]:= true;
    r[i shl 1 - 1].x:= x;
    r[i shl 1 - 1].y:= y;
    r[i shl 1].x:= y;
    r[i shl 1].y:= x;
  end;
  m:= m shl 1;
  for i:= 1 to m do
  begin
    if (sx = r[i].x) and (sy = r[i].y) then s:= i;
    if (fx = r[i].x) and (fy = r[i].y) then f:= i;
  end;

end;

begin
  reset(input, cinfile);
  rewrite(output, coutfile);
  readdata;
  solve;
  outdata;
  close(output);
  close(input);
end.
