{$I-,Q-,R-,S-}
program Project1;

{$APPTYPE CONSOLE}

Var
        n, m : LongInt;
        abeg, bbeg, aen, ben, beg, en : LongInt;
        v1, v2, d, v11, pr, v22 : Array[1..4000] Of LongInt;
        us : Array[1..4000] Of Boolean;
        A : Array[1..2001, 1..2001] Of ShortInt;
        A1 : Array[1..101, 1..101] Of LongInt;
        

Procedure InputData;

Var
        i : LongInt;
        
Begin
        Assign(Input, 'kingdom.in');
        Reset(input);
        Read(n, m, abeg, bbeg, aen, ben);
        For i:= 1 To M Do
                Read(v1[i], v2[i]);
        Close(input);
End;

Procedure Solve;

Var
        n1, i, j, min, num : LongInt;
        
Begin
        n1:= 0;
        FillChar(A, SizeOf(A), 0);
        FillChar(A1, SizeOf(A1), 0);

        For i:= 1 To M Do
        Begin
                Inc(n1);
                v11[n1]:= v1[i];
                v22[n1]:= v2[i];
                If (v11[n1] = abeg) and (v22[n1] = bbeg) then
                        beg:= n1;
                If (v11[n1] = aen) and (v22[n1] = ben) then
                        en:= n1;

                Inc(n1);

                v22[n1]:= v1[i];
                v11[n1]:= v2[i];
                 If (v11[n1] = abeg) and (v22[n1] = bbeg) then
                        beg:= n1;
                If (v11[n1] = aen) and (v22[n1] = ben) then
                        en:= n1;

                A1[v1[i], v2[i]]:= 1;
                A1[v2[i], v1[i]]:= 1;
        End;

        For i:= 1 To n1 Do
         For j:= 1 To n1 Do
         if (v11[i] <> v22[j]) or (v22[i] <> v11[j]) Then
         Begin

                If (A1[V11[i], V11[j]] = 1) And (V22[i] = V22[j]) Then
                        A[i, j]:= 1 Else
                If (A1[V22[i], V22[j]] = 1) And (V11[i] = V11[j]) Then
                        A[i, j]:= 1 Else
                If (A1[V22[i], V22[j]] = 1) And (A1[V11[i], V11[j]] = 1) Then
                        A[i, j]:= 2;
         End;

        FillChar(Us, SizeOf(Us), False);
        FillChar(Pr, SizeOf(Pr), 0);

        For i:= 1 To n1 Do
                D[i]:= 1000000;
        D[beg]:= 0;
        FOr i:= 1 To n1 Do
        Begin
                Min:= 1000000;
                Num:= 0;
                For j:= 1 To n1 Do
                 If D[j] < Min Then
                  If Not Us[j] Then
                  Begin
                        Min:= D[j];
                        Num:= j;
                  end;
                 If Num = 0 Then
                        Break;
                 Us[num]:= True;
                 For j:= 1 To n1 Do
                  If Not Us[j] Then
                   If A[i, j] <> 0 Then
                  If D[j] > D[i] + A[i, j] Then
                  Begin
                   D[j]:= D[i] + A[i, j];
                   Pr[j]:= i;
                  End;
        End;
End;

Procedure OutputData;

Var
        num, i, kol : LongInt;
        Otv : Array[1..4000, 1..2] Of LongInt;
        
Begin
        Assign(output, 'kingdom.out');
        Rewrite(Output);
        Num:= En;
        Kol:= 0;
        While Num <> 0 Do
        Begin
                Inc(Kol);
                Otv[Kol, 1]:= V11[num];
                Otv[Kol, 2]:= V22[num];

                Num:= Pr[num];
        End;
        Writeln(D[en], ' ', kol);
        For i:= Kol DownTo 1 Do
                Writeln(Otv[i, 1], ' ', Otv[i, 2]);

        Close(output);
End;

begin
  InputData;
  Solve;
  OutputData;
end.
