const
 fin='kingdom.in';
 fout='kingdom.out';

Var
 I,J, N, M,A1,B1,A2,B2, K : LongInt;
 F:array[1..100,1..100] of Byte;

 g:array[1..2000,1..2000] of Byte;

 A, B:array[1..2000] of Byte;
 X,Y,S,D : LongInt;

 Min, Flag, Pred,T:array[1..2000] of LongInt;

procedure Solve;
Var
  I,V,U,M,L:Longint;
Begin
   FOr I:=1 to K do Min[I]:=100000;
   Min[S]:=0;
   While true do
   Begin
     U:=-1; M:=100000;
     for V:=1 to K do
       if (Flag[V]=0)and(M>Min[V]) then
       Begin
        U:=V; M:=Min[V];
       End;
    if (U=D) then break;
    Flag[U]:=1;
    For V:=1 To K do
      if (G[U,V]>0)and(Min[V]>M+G[U,V]) then
      Begin
         Min[V]:=M+G[U,V];
         Pred[V]:=U;
      End;
   End;
  L:=0; Write(Min[D],' '); U:=D;
  While (U<>0) do
  Begin
   Inc(L);
   T[L]:=U;
   U:=Pred[U];
  End;
  WriteLn(L);
  For I:=L downto 1 do WriteLn(A[T[I]],' ',B[T[I]]);
End;

begin
 assign(Input,fin); reset(input);
 assign(Output,fout); rewrite(output);
 readln(N, M,A1,B1,A2,B2);
 K:=0;
 For I:=1 To M do
 Begin
   read(X,Y); Inc(K); f[x,y]:=1; f[y,x]:=1;

   A[K]:=X; B[K]:=Y;
   if (X=A1)and(Y=B1) then S:=K;
   if (X=A2)and(Y=B2) then D:=K;
   Inc(K);
   A[K]:=Y; B[K]:=X;
   if (Y=A1)and(X=B1) then S:=K;
   if (Y=A2)and(X=B2) then D:=K;
 End;
 For i:=1 TO k DO
   fOR j:=i+1 tO k DO
   Begin
    if (A[J]=B[I])and(B[J]=A[I]) then continue;
    if (A[I]<>A[J])and(B[I]<>B[J]) and
    (F[A[I], A[J]]=1)and(F[B[I], B[J]]=1) then
    Begin
     G[I,J]:=2;
     G[J,I]:=2;
    End;
    if (A[I]=A[j])and(F[B[I],B[J]]=1) then
    Begin
     G[I,J]:=1;
     G[J,I]:=1;
    End;
    if (B[I]=B[j])and(F[A[I],A[J]]=1) then
    Begin
     G[I,J]:=1;
     G[J,I]:=1;
    End;
   End;
 Solve;  
 close(input); close(output);
end.