program pk;

const infile  = 'kingdom.in';
      outfile = 'kingdom.out';
      maxn    = 100;

var g : array[1..maxn, 1..maxn]of byte;
    inf : array[1..maxn, 1..maxn]of record
                 mintime : longint;
                 la, lb  : longint;
               end;
    q : array[1..3] of record
          c : longint;
          a, b : array[1..maxn*maxn]of longint;
         end;        
    n, m, a1, b1, a2, b2, time : longint;

procedure init;
var i, a, b : longint;
 begin
  assign(input, infile); reset(input);
  assign(output, outfile); rewrite(output);
  read(n, m, a1, b1, a2, b2);
  fillchar(g, sizeof(g), 0);
  for i := 1 to m do begin
    read(a, b);
    g[a, b] := 1;
    g[b, a] := 1;
   end;
  for a := 1 to n do
   for b := 1 to n do inf[a, b].mintime := -1;
  inf[a1, b1].mintime := 0;
  time := 0;
  for i := 1 to 3 do q[i].c := 0;
 end;

procedure solve;
var ind, i, ai, bi, i1, i2, a, b : longint;
 begin
  q[1].c := 1;
  q[1].a[1] := a1;
  q[1].b[1] := b1;
  ind := 0;
  while inf[a2, b2].mintime = -1 do begin

    if time > 0 then q[ind].c := 0;

    ind := ind + 1; if ind > 3 then ind := 1;
    i1 := ind + 1; if i1 > 3 then i1 := 1;
    i2 := i1 + 1; if i2 > 3 then i2 := 1;

    for i := 1 to q[ind].c do begin
      a := q[ind].a[i]; b := q[ind].b[i];

      for ai := 1 to n do
       if (g[ai, a] + g[ai, b] = 2) and (ai <> a) and (ai <> b) and
          ((inf[ai, b].mintime = -1) or (inf[ai, b].mintime > time + 1)) then begin
            inf[ai, b].mintime := time + 1;
            inf[ai, b].la := a;
            inf[ai, b].lb := b;
            q[i1].c := q[i1].c + 1;
            q[i1].a[q[i1].c] := ai;
            q[i1].b[q[i1].c] := b;
           end;

      for bi := 1 to n do
       if (g[bi, b] + g[bi, b] = 2) and (bi <> b) and (bi <> a) and
          ((inf[a, bi].mintime = -1) or (inf[a, bi].mintime > time + 1)) then begin
            inf[a, bi].mintime := time + 1;
            inf[a, bi].la := a;
            inf[a, bi].lb := b;
            q[i1].c := q[i1].c + 1;
            q[i1].a[q[i1].c] := a;
            q[i1].b[q[i1].c] := bi;
           end;

       for ai := 1 to n do
       for bi := 1 to n do if (g[ai, bi] = 1) and (not ((ai = b) and (bi = a))) and (ai <> bi) then
       if (g[bi, b] + g[ai, a] = 2) and (bi <> b) and (ai <> a) and
          ((inf[ai, bi].mintime = -1) or (inf[ai, bi].mintime > time + 2)) then begin
            inf[ai, bi].mintime := time + 2;
            inf[ai, bi].la := a;
            inf[ai, bi].lb := b;
            q[i2].c := q[i2].c + 1;
            q[i2].a[q[i2].c] := ai;
            q[i2].b[q[i2].c] := bi;
           end;

     end;

    time := time + 1;
   end;
 end;

var path : array[1..maxn*maxn, 1..2]of longint;
    plen : longint;

procedure save;
var ca, cb, x, y : longint;
 begin
  plen := 0;
  ca := a2; cb := b2;
  while true do begin
    plen := plen + 1;
    path[plen, 1] := ca;
    path[plen, 2] := cb;
    if (ca = a1) and (cb = b1) then break;
    x := inf[ca, cb].la; y := inf[ca, cb].lb;
    ca := x; cb := y;
   end;
  writeln(inf[a2, b2].mintime, ' ', plen);
  for x := plen downto 1 do writeln(path[x, 1], ' ', path[x, 2]);
  close(output);
 end;

begin
 init;
 solve;
 save;
end.