{$apptype console}

uses
  Math;

const
  Q_SIZE = 100000;

type
  TPortal = record
    a, b: integer;
  end;
  TState = record
    prev: integer;
    step: integer;
  end;

procedure next(var t: integer);
begin
  t := t mod Q_SIZE + 1;
end;

var
  i, j: integer;
  n, m: integer;
  aa, bb: integer;
  cc: integer;
  c: array[1..100, 1..100] of integer;

  a1, b1, a2, b2: integer;
  s: array[1..10000] of TState;
  p: array[1..20000] of TPortal;

  q: array[1..Q_SIZE] of integer;
  b, e: integer;

  pos: integer;

procedure moveto(cur, new: integer; doub: boolean = false);
var
  step: integer;
begin
  step := s[cur].step + 1;
  if doub then Inc(step);

  if s[new].step > step then begin
    s[new].step := step;
    s[new].prev := cur;

    q[e] := new;
    next(e);
  end;
end;

begin
  Assign(input, 'kingdom.in');
  Assign(output, 'kingdom.out');
  Reset(input);
  Rewrite(output);

  Read(n, m, a1, b1, a2, b2);

  FillChar(c, sizeof(c), 0);
  
  for i := 1 to m do begin
    Read(aa, bb);
    c[aa, bb] := i;
    c[bb, aa] := m + i;

    p[i].a := aa;
    p[i].b := bb;
    p[m + i].a := bb;
    p[m + i].b := aa;
  end;

  for i := 1 to High(s) do s[i].step := MaxInt;

  b := 1;
  e := 2;
  q[b] := c[a1, b1];

  s[q[b]].step := 0;
  s[q[b]].prev := 0;

  while b <> e do begin
    pos := q[b];
    next(b);

    aa := p[pos].a;
    bb := p[pos].b;

    for i := 1 to n do begin
      if (c[aa, i] <> 0) and (c[i, bb] <> 0) then
        moveto(pos, c[i, bb]);
      if (c[bb, i] <> 0) and (c[aa, i] <> 0) then
        moveto(pos, c[aa, i]);

      for j := 1 to n do 
        if 
          (c[aa, i] <> 0) and (c[bb, j] <> 0) and (c[i, j] <> 0) and ((aa <> j) or (bb <> i))
        then 
          moveto(pos, c[i, j], true);
    end;
  end;

  b := 1;
  e := 2;
  q[b] := c[a2, b2];

  cc := s[q[b]].step;
  while q[e - 1] <> c[a1, b1] do begin
    bb := q[e - 1];
    aa := s[bb].prev;

    q[e] := aa;

    next(e);
  end;

  WriteLn(cc, ' ', e - b);
  for i := e - 1 downto 1 do WriteLn(p[q[i]].a, ' ', p[q[i]].b);

  Close(input);
  Close(output);
end.
