program prK;

const
  INF = 1000000000;

var
  n, m: Integer;
  a1, b1, a2, b2, s, f: Integer;
  sp: array[0..1000, 0..1] of Integer;
  ms: array[0..100, 0..128] of Boolean;
  i, x, y: Integer;
  tw: Integer;
  t: array[0..2000] of Boolean;
  d: array[0..2000] of Integer;
  p: array[0..2000] of Integer;
  dm, wa, im: Integer;
  am, bm, ac, bc: Integer;
  w: array[0..2000, 0..1] of Integer;
  wc: Integer;

begin
  Assign(Input, 'kingdom.in');
  Reset(Input);
  Assign(Output, 'kingdom.out');
  Rewrite(Output);

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

  FillChar(ms, SizeOf(ms), False);
  s := 0;
  f := 0;
  for i := 0 to m - 1 do
  begin
    Read(x, y);
    if (x = a1) and (y = b1) then s := i * 2;
    if (x = b1) and (y = a1) then s := i * 2 + 1;
    if (x = a2) and (y = b2) then f := i * 2;
    if (x = b2) and (y = a2) then f := i * 2 + 1;
    Dec(x);
    Dec(y);
    sp[i, 0] := x;
    sp[i, 1] := y;
    ms[x, y] := True;
    ms[y, x] := True;
  end;

  { Deikstra }

  for i := 0 to m * 2 - 1 do d[i] := INF;
  d[s] := 0;

  tw := m * 2;
  FillChar(t, SizeOf(t), True);
  
  while tw > 0 do
  begin
    dm := INF;
    im := -1;
    for i := 0 to m * 2 - 1 do
      if t[i] and ((dm = INF) or (d[i] < dm)) then
      begin
        dm := d[i];
        im := i;
      end;
    if dm = INF then Break;
    if Odd(im) then
    begin
      am := sp[im shr 1, 1];
      bm := sp[im shr 1, 0];
    end
    else begin
      am := sp[im shr 1, 0];
      bm := sp[im shr 1, 1];
    end;
//    WriteLn(am + 1, ' ', bm + 1, ' len = ', dm);
    t[im] := False;
    Dec(tw);
    for i := 0 to m * 2 - 1 do
    begin
      if Odd(i) then
      begin
        ac := sp[i shr 1, 1];
        bc := sp[i shr 1, 0];
      end
      else begin
        ac := sp[i shr 1, 0];
        bc := sp[i shr 1, 1];
      end;
      wa := Inf;
      if (am = ac) and (bm <> bc) and ms[bm, bc] then wa := 1
      else if (am <> ac) and (bm = bc) and ms[am, ac] then wa := 1
      else if ((am <> bc) or (bm <> ac)) and ms[am, ac] and ms[bm, bc] then wa := 2;
      if t[i] and (wa <> Inf) and (dm + wa < d[i]) then
      begin
//        WriteLn(ac + 1, ' ', bc + 1, ' upd len = ', dm + wa);
        d[i] := dm + wa;
        p[i] := im;
      end;
    end;
  end;

  { Pathfinder }

  wc := 0;

  i := f;
  while i <> s do
  begin
    if Odd(i) then
    begin
      w[wc, 0] := sp[i shr 1, 1];
      w[wc, 1] := sp[i shr 1, 0];
    end
    else begin
      w[wc, 0] := sp[i shr 1, 0];
      w[wc, 1] := sp[i shr 1, 1];
    end;
    Inc(wc);
    i := p[i];
  end;
  w[wc, 0] := sp[i shr 1, 0];
  w[wc, 1] := sp[i shr 1, 1];
  Inc(wc);

  WriteLn(d[f], ' ', wc);
  for i := wc - 1 downto 0 do WriteLn(w[i, 0] + 1, ' ', w[i, 1] + 1);
end.
