{$apptype console}

const
  inf = 1000000000;
  qlen = 1000001;

var
  n, m, a1, b1, a2, b2, a, b, i, j, h, t: integer;
  g, mask: array[1..105, 1..105] of boolean;
  c, pa, pb, kk: array[1..105, 1..105] of integer;
  qa, qb: array[1..qlen] of integer;

procedure printans(a, b: integer);
begin
  if pa[a, b] <> 0 then
    printans(pa[a, b], pb[a, b]);
  writeln(a, ' ', b);
end;

begin
  assign(input, 'kingdom.in'); reset(input);
  assign(output, 'kingdom.out'); rewrite(output);

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

  fillchar(g, sizeof(g), false);
  for i := 1 to m do begin
    read(a, b);
    g[a, b] := true;
    g[b, a] := true;
  end;

  for a := 1 to n do
    for b := 1 to n do begin
      c[a, b] := inf;
      pa[a, b] := 0;
      pb[a, b] := 0;
      kk[a, b] := 0;
      mask[a, b] := true;
    end;

  h := 1;
  t := 2;
  qa[h] := a1;
  qb[h] := b1;
  c[a1, b1] := 0;
  mask[a1, b1] := false;
  kk[a1, b1] := 1;

  while h <> t do begin
    a := qa[h];
    b := qb[h];
    mask[a, b] := true;
    inc(h);
    if h > qlen then
      h := 1;
    for i := 1 to n do begin
  {1}
      if g[a, i] and (i <> b) and g[i, b] then begin
        if c[a, b] + 1 < c[i, b] then begin
          c[i, b] := c[a, b] + 1;
          pa[i, b] := a;
          pb[i, b] := b;
          kk[i, b] := kk[a, b] + 1;
          if mask[i, b] then begin
            mask[i, b] := false;
            qa[t] := i;
            qb[t] := b;
            inc(t);
            if t > qlen then
              t := 1;
          end;
        end;
      end;
   {2}
      if g[b, i] and (i <> a) and g[i, a] then begin
        if c[a, b] + 1 < c[a, i] then begin
          c[a, i] := c[a, b] + 1;
          pa[a, i] := a;
          pb[a, i] := b;
          kk[a, i] := kk[a, b] + 1;
          if mask[a, i] then begin
            mask[a, i] := false;
            qa[t] := a;
            qb[t] := i;
            inc(t);
            if t > qlen then
              t := 1;
          end;
        end;
      end;
    end;

{3}
    for i := 1 to n do
      for j := 1 to n do
        if (i <> j) and (i <> a) and (j <> b) and ((i <> b) or (j <> a)) and
           g[a, i] and g[b, j] and g[i, j] then begin
          if c[a, b] + 2 < c[i, j] then begin
            c[i, j] := c[a, b] + 2;
            pa[i, j] := a;
            pb[i, j] := b;
            kk[i, j] := kk[a, b] + 1;
            if mask[i, j] then begin
              mask[i, j] := false;
              qa[t] := i;
              qb[t] := j;
              inc(t);
              if t > qlen then
                t := 1;
            end;
          end;
        end;
  end;

  if c[a2, b2] >= inf then
    runerror(239);

  writeln(c[a2, b2], ' ', kk[a2, b2]);
  printans(a2, b2);
end.
