
{$APPTYPE CONSOLE}

Var ans,I,J,K,L,N,M,q,p,a1,b1,a2,b2,a,b,aa,bb:Longint;
    d: array[1..100, 1..100] of longint;
    q1l, q2l: array[0..1] of longint;
    q1a, q1b, q2a, q2b, q2aa, q2bb: array[0..1, 1..10000] of longint;
    p1, p2: array[1..1000] of longint;
    nxc: array[1..100] of longint;
    nx: array[1..100, 1..100] of longint;
    reva, revb: array[1..100, 1..100] of longint;
    outa, outb: array[1..10000] of longint;
    adj: array[1..100, 1..100] of boolean;
begin
  Assign(input,'kingdom.in');
  Reset(input);
  Assign(output,'kingdom.out');
  ReWrite(output);
  read(n, m, a1, b1, a2, b2);
  fillchar(nxc, sizeof(nxc), 0);
  fillchar(adj, sizeof(adj), 0);
  for i := 1 to m do
  begin
    read(p1[i], p2[i]);
    adj[p1[i], p2[i]] := true;
    adj[p2[i], p1[i]] := true;
    inc(nxc[p1[i]]);
    nx[p1[i], nxc[p1[i]]] := p2[i];
    inc(nxc[p2[i]]);
    nx[p2[i], nxc[p2[i]]] := p1[i];
  end;
  fillchar(d, sizeof(d), 0);
  for i := 1 to n do
    d[i, i] := -1;
  d[a2, b2] := 1;
  q1l[0] := 1;
  q1a[0, 1] := a2;
  q1b[0, 1] := b2;
  q2l[0] := 0;
  q2l[1] := 0; 
  q := 0;
  while d[a1, b1]=0 do
  begin
    while q2l[q]>0 do
    begin
      a := q2a[q,q2l[q]];
      b := q2b[q,q2l[q]];
      aa := q2aa[q,q2l[q]];
      bb := q2bb[q,q2l[q]];
      dec(q2l[q]);
      if (d[aa,bb]=0) then
      begin
        d[aa,bb] := 2+d[a,b];
        reva[aa,bb] := a;
        revb[aa,bb] := b;
      end;
      inc(q1l[q]);
      q1a[q, q1l[q]] := aa;
      q1b[q, q1l[q]] := bb;
    end;
    p := 1-q;
    q1l[p] := 0;
    while q1l[q]>0 do
    begin
      a := q1a[q, q1l[q]];
      b := q1b[q, q1l[q]];
      dec(q1l[q]);
      for i := 1 to nxc[a] do
      begin
        aa := nx[a, i];
        if not adj[aa,b] then
          continue;
        if d[aa,b]=0 then
        begin
          d[aa,b] := d[a, b]+1;
          inc(q1l[p]);
          q1a[p, q1l[p]] := aa;
          q1b[p, q1l[p]] := b;
          reva[aa,b] := a;
          revb[aa,b] := b;
        end;
      end;
      for i := 1 to nxc[b] do
      begin
        bb := nx[b, i];
        if not adj[a,bb] then
          continue;
        if d[a,bb]=0 then
        begin
          d[a,bb] := d[a, b]+1;
          inc(q1l[p]);
          q1a[p, q1l[p]] := a;
          q1b[p, q1l[p]] := bb;
          reva[a,bb] := a;
          revb[a,bb] := b;
        end;
      end;
      for i := 1 to nxc[a] do
        for j := 1 to nxc[b] do
        begin
          aa := nx[a, i];
          bb := nx[b, j];
          if (not adj[aa,bb]) or (aa=b) and (bb=a) then
            continue;
          inc(q2l[q]);
          q2aa[q, q2l[q]] := aa;
          q2bb[q, q2l[q]] := bb;
          q2a[q, q2l[q]] := a;
          q2b[q, q2l[q]] := b;
        end;
    end;
    q := p;
  end;
  write(d[a1, b1]-1, ' ');
  a := a1;
  b := b1;
  ans := 1;
  outa[1] := a;
  outb[1] := b;
  while (a<>a2) or (b<>b2) do
  begin
    inc(ans);
    aa := reva[a, b];
    bb := revb[a, b];
{    if ((aa<>a2) or (bb<>b2)) then
    begin
      if ((aa=a) and (revb[aa,bb]=bb))
      or ((bb=b) and (reva[aa,bb]=aa)) then
      begin
        a := reva[aa, bb];
        b := revb[aa, bb];
      end
      else
      begin
        a := aa;
        b := bb;
      end;
    end
    else
    begin}
      a := aa;
      b := bb;
{   end;}
    outa[ans] := a;
    outb[ans] := b;
  end;
  writeln(ans);
  for i := 1 to ans do
    writeln(outa[i], ' ', outb[i]);
  Close(input);
  Close(output);
end.
