uses
  SysUtils;

var
  i, x, y, j, m, n, a1, a2, b1, b2: integer;
  a: array[1 .. 100, 1 .. 100] of byte;
  b: array[0 .. 100, 0 .. 1000] of integer;
  Cur1, Cur2, Best1, Best2: array[1 .. 1000] of integer;
  Max, Cur: integer;
  Kol, KolMax: integer;

  procedure Rec(a1, b1, Cur, CurKol: integer);
  var
    i, j, d: integer;
  begin
    Inc(CurKol);
    if Cur > Max then Exit;
    Cur1[CurKol] := a1;
    Cur2[CurKol] := b1;
    if (a1 = a2) and (b1 = b2) then
    begin
      if Cur < Max then
      begin
        Best1 := Cur1;
        Best2 := Cur2;
        Max := Cur;
        KolMax := CurKol;
      end;
    end else
    begin
      for i := 1 to b[a1, 0] do
      begin
        for j := 1 to b[b1, 0] do
        begin
          if a[b[a1, i], b[b1, j]] = 1 then
          begin
            d := 2;
            if a1 = b[a1, i] then Dec(d);
            if b1 = b[b1, i] then Dec(d);
            if (a1 = b[b1, i]) and (b1 = b[a1, i]) then d := 0;
            if d <> 0 then
              Rec(b[a1, i], b[b1, j], Cur + d, CurKol);
          end;
        end;
      end;
    end;
  end;

begin
  assignfile(input, 'kingdom.in');
  assignfile(output, 'kingdom.out');
  reset(input);
  rewrite(output);
  read(n, m, a1, b1, a2, b2);
  fillchar(a, sizeof(a), 0);
  fillchar(b, sizeof(b), 0);
  for i := 1 to m do
  begin
    read(x, y);
    a[x, y] := 1;
    a[y, x] := 1;
    b[x, 0] := b[x, 0] + 1;
    b[x, b[x, 0]] := y;
    b[y, 0] := b[y, 0] + 1;
    b[y, b[y, 0]] := x;
  end;
  for i := 1 to m do
  begin
    b[i, 0] := b[i, 0] + 1;
    b[i, b[i, 0]] := i;
  end;
  Max := m;
  Rec(a1, b1, 0, 0);
  Writeln(Max, ' ', KolMax);
  for i := 1 to KolMax do
  begin
    writeln(Best1[i], ' ', Best2[i]);
  end;
  closefile(input);
  closefile(output);
end.
