const
 MaxN = 100;
 QL = 100000;

type
 Byte = LongInt;
 Integer = LongInt;
 PList = ^TList;
 TList = record
  V: Byte;
  Next: PList;
 end;

procedure Add(var P: PList; X: Byte);
var
 Q: PList;
begin
 New(Q);
 Q^.V:=X;
 Q^.Next:=P;
 P:=Q;
end;

var
 N, M, i, j, k, s1, s2, f1, f2, qb, qe: LongInt;
 A: array [1..MaxN] of PList;
 Q: array [1..QL, 1..2] of Byte;
 G: array [1..MaxN, 1..MaxN] of Byte;
 L: array [0..MaxN, 0..MaxN] of Integer;
 E: array [0..MaxN, 0..MaxN] of Integer;
 InQ: array [1..MaxN, 1..MaxN] of Boolean;
 P: array [1..MaxN, 1..MaxN, 1..2] of Byte;

procedure WriteAns(V1, V2: Byte);
begin
 If P[V1, V2, 1] <> 0 then WriteAns(P[V1, V2, 1], P[V1, V2, 2]);
 WriteLn(V1, ' ', V2);
end;

procedure Push(U1, U2, P1, P2: Byte; Dist: Integer);
begin
 If (L[U1, U2] <= L[P1, P2]+Dist) then Exit;
 E[U1, U2]:=E[P1, P2]+1;
 L[U1, U2]:=L[P1, P2]+Dist;
 P[U1, U2, 1]:=P1;
 P[U1, U2, 2]:=P2;
 If (U1 = F1) and (U2 = F2) then
  begin
   WriteLn(L[U1, U2], ' ', E[U1, U2]);
   WriteAns(U1, U2);
   Halt(0);
  end;
 If not InQ[U1, u2] then
  begin
   inc(qe);
   If qe > QL then qe:=1;
   Q[qe][1]:=u1;
   Q[qe][2]:=u2;
  end;
end;

procedure Pop(var U1, U2: Byte);
begin
 inc(qb);
 If qb > QL then qb:=1;
 U1:=Q[qb][1];
 U2:=Q[qb][2];
end;

procedure BFS(V1, V2: Byte);
var
 P, Q: PList;
begin
 Push(V1, V2, 0, 0, 0);
 Repeat
  Pop(V1, V2);
  P:=A[V1];
  While P <> Nil do
   begin
    If (P^.V <> V2) and (G[P^.V, V2] = 1) then Push(P^.V, V2, V1, V2, 1);
    P:=P^.Next;
   end;
  Q:=A[V2];
  While Q <> Nil do
   begin
    If (V1 <> Q^.V) and (G[V1, Q^.V] = 1) then Push(V1, Q^.V, V1, V2, 1);
    Q:=Q^.Next;
   end;
  P:=A[V1];
  While P <> Nil do
   begin
    Q:=A[V2];
    While Q <> Nil do
     begin
      If (P^.V <> Q^.V) and (G[P^.V, Q^.V] = 1) and ([V1, P^.V] <> [V2, Q^.V]) then
       Push(P^.V, Q^.V, V1, V2, 2);
      Q:=Q^.Next;
     end;
    P:=P^.Next;
   end;
 until qb = qe;
end;

begin
 Assign(Input, 'kingdom.in');
 Reset(Input);
 Assign(output, 'kingdom.out');
 ReWrite(Output);
 ReadLn(N, M, S1, S2, F1, F2);
 FillChar(G, SizeOf(G), 0);
 For i:=1 to M do
  begin
   Read(j, k);
   G[j, k]:=1;
   G[k, j]:=1;
   Add(A[j], k);
   Add(A[k], j);
  end;
 For i:=1 to N do
  For j:=1 to N do
   L[i, j]:=MaxLongInt div 3;
 BFS(S1, S2);
end.
