program k;

{$APPTYPE CONSOLE}
{.$R+}

var
  N, M, A1, A2, B1, B2: Integer;
  E: array[1..2000] of record A, B: Integer; end;
  G: array[1..100, 1..100] of Boolean;

procedure Inp;
var
  I:Integer;
begin
  FillChar(G, sizeof(G), 0);

  Read(N, M, A1, B1, A2, B2);
  for I:=1 to 1000 do
    Read(E[I].A, E[I].B);

  for I:=M+1 to 2*M do
    begin
      E[I].A:=E[I-M].B;
      E[I].B:=E[I-M].A;
      G[E[I].A, E[I].B]:=True;
      G[E[I].B, E[I].A]:=True;
    end;
  M:=M*2;
end;

var
  D: array[1..2000] of Integer;
  F: array[1..2000] of Integer;
  W: array[1..2000] of Boolean;

function CanGo(A1, B1, A2, B2: Integer):Integer;
begin
  CanGo:=0;
  if (G[A2, B2] = False) or
     ((G[A1, A2] = False) and (A1 <> A2)) or
     ((G[B1, B2] = False) and (B1 <> B2)) then Exit;
  if (A1 = B2) and (B1 = A2) then Exit;
  CanGo:=Ord(A1<>A2) + Ord(B1<>B2);
end;

var
  P: array[1..10000] of Integer;
  NP: Integer;

procedure Run;
var
  I, Last, Min: Integer;
  L: Integer;
begin
  FillChar(D, Sizeof(D), $FF);
  FillChar(F, sizeof(F), 0);

  for I:=1 to M do
    if (E[I].A = A1) and (E[I].B = B1) then
      begin
        D[I]:=0;
        Break;
      end;

  Last:=0;
  for I:=1 to M do
    if (E[I].A = A2) and (E[I].B = B2) then
      begin
        Last:=I;
        Break;
      end;

  repeat
    Min:=-1;
    for I:=1 to M do
      if (W[I] = False) and (D[I] <> -1) and ((Min = -1) or (D[I] < D[Min])) then Min:=I;

    if Min = -1 then Break;
    W[Min]:=True;

    for I:=1 to M do
      begin
        L:=CanGo(E[Min].A, E[Min].B, E[I].A, E[I].B);
        if (L <> 0) and ((D[I] = -1) or (D[I] > D[Min] + L)) then
          begin
            D[I]:=D[Min]+L;
            F[I]:=Min;
          end;
      end;
  until false;


  NP:=0;
  I:=Last;

  while (I <> 0) do
   begin
     Inc(NP);
     P[NP]:=I;
     I:=F[I];
   end;

  WriteLn(D[Last], ' ', NP);
  for i:=NP downto 1 do
    WriteLn(E[P[I]].A, ' ', E[P[I]].B);
end;

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

  Assign(Output, 'kingdom.out');
  ReWrite(Output);

  Inp;
  Run;
end.
