{$APPTYPE CONSOLE}
{$O-,Q+,R+}

uses Math, SysUtils;

type
  int = integer;
  bool = boolean;
  real = extended;
const
  inf = 1 shl 30;
var
  w, n, m, a1, b1, a2, b2, k, i, st, fi, j : int;
  p1, p2, dist, prev : array[1..2000] of int;
  u, v : array[1..2001] of int;
  mark : array[1..2000] of bool;
  num, we : array[1..2000, 1..2000] of int;
begin
  {
  rewrite(output, 'kingdom.in');
  writeln('100 1000 1 2 99 100');
  writeln('1 2');
  writeln('99 100');
  for i := 3 to 1000 do
    writeln(random(100) + 1, ' ', random(100) + 1);
  exit;
  }
  reset(input, 'kingdom.in');
  rewrite(output, 'kingdom.out');
  read(n, m, a1, b1, a2, b2);
  k := 0;
  for i := 1 to m do
  begin
    inc(k);
    read(p1[k], p2[k]);
    num[p1[k]][p2[k]] := k;

    inc(k);
    p1[k] := p2[k - 1];
    p2[k] := p1[k - 1];
    num[p1[k]][p2[k]] := k;
  end;
  st := num[a1][b1];
  fi := num[a2][b2];
  for i := 1 to k do
    for j := 1 to k do
      if ((p1[i] = p1[j]) and (p2[i] = p2[j]))
         or ((p1[i] = p2[j]) and (p2[i] = p1[j])) then
        we[i][j] := inf
      else if ((p1[i] = p1[j]) and (num[p2[i]][p2[j]] <> 0))
              or ((num[p1[i]][p1[j]] <> 0) and (p2[i] = p2[j])) then
        we[i][j] := 1
      else if (num[p1[i]][p1[j]] <> 0) and (num[p2[i]][p2[j]] <> 0) then
        we[i][j] := 2
      else
        we[i][j] := inf;

  for i := 1 to k do
  begin
    mark[i] := false;
    dist[i] := inf;
  end;
  dist[st] := 0;
  while true do
  begin
    i := -1;
    for j := 1 to k do
      if (not mark[j]) and ((i = -1) or (dist[i] > dist[j])) then
        i := j;
    assert((i <> -1) and (dist[i] < inf));
    if i = fi then
      break;
    mark[i] := true;
    for j := 1 to k do
      if dist[j] > dist[i] + we[i][j] then
      begin
        dist[j] := dist[i] + we[i][j];
        prev[j] := i;
      end;
  end;
  w := 0;
  write(dist[fi]);
  while fi <> st do
  begin
    inc(w);
    u[w] := p1[fi];
    v[w] := p2[fi];
    fi := prev[fi];
  end;
  inc(w);
  u[w] := p1[st];
  v[w] := p2[st];
  writeln(' ', w);
  for i := w downto 1 do
    writeln(u[i], ' ', v[i]);
end.