program k;

{$APPTYPE CONSOLE}
{$R+,Q+,S+,H+}

uses
  Math,
  SysUtils;

Type
  Integer=LongInt;
  Real=Extended;

Const
  TaskID='kingdom';
  InFile=TaskID+'.in';
  OutFile=TaskID+'.out';
  MaxN=102;
  MaxM=1002;
  MaxQueue=MaxM*10;

Type
  TPos=Record
    P1,P2:Integer;
  End;

Var
  N,M:Integer;
  S,T:TPos;
  G:Array[1..MaxN,1..MaxN]Of Integer;
  NE:Array[1..MaxN]Of Integer;
  E:Array[1..MaxN,1..MaxM]Of Integer;
  D:Array[1..MaxN,1..MaxN]Of Integer;
  Prev:Array[1..MaxN,1..MaxN]Of TPos;
  Got:Array[1..MaxN,1..MaxN]Of Boolean;
  Qu:Array[0..2,1..MaxQueue]Of TPos;
  QNum:Array[0..2]Of Integer;
  NPath:Integer;
  Path:Array[1..MaxQueue]Of TPos;
  Infinity:Integer;

Procedure Load;
Var
  I:Integer;
  A,B:Integer;
Begin
  ReSet(Input,InFile);
  Read(N,M);
  Read(S.P1,S.P2,T.P1,T.P2);
  FillChar(G,SizeOf(G),0);
  FillChar(NE,SizeOf(NE),0);
  For I:=1 To M Do Begin
    Read(A,B);
    Inc(G[A,B]);
    Inc(G[B,A]);
    Inc(NE[A]);
    E[A,NE[A]]:=B;
    Inc(NE[B]);
    E[B,NE[B]]:=A;
  End;
  Close(Input);
End;

Procedure Otkat(T:TPos);
Begin
  If D[T.P1,T.P2]>0 Then
    Otkat(Prev[T.P1,T.P2]);
  Inc(NPath);
  Path[NPath]:=T;
End;

Procedure Solve;
Var
  I,J,JJ,C,N1,N2,Dst,CD:Integer;
  P,NP:TPos;
Begin
  Qu[0,1]:=S;
  QNum[0]:=1;
  QNum[1]:=0;
  QNum[2]:=0;
  FillChar(D,SizeOf(D),127);
  FillChar(Got,SizeOf(Got),False);
  Infinity:=D[1,1];
  D[S.P1,S.P2]:=0;
  C:=0;
  While Not Got[T.P1,T.P2] Do Begin
    N1:=(C+1) Mod 3;
    N2:=(C+1) Mod 3;
    For I:=1 To QNum[C] Do Begin
      P:=Qu[C,I];
      If Got[P.P1,P.P2] Then Continue;
      Got[P.P1,P.P2]:=True;
      CD:=D[P.P1,P.P2];
      For J:=1 To NE[P.P1] Do Begin
        NP:=P;
        NP.P1:=E[P.P1,J];
        If (G[NP.P1,NP.P2]>0) Then Begin
          If D[NP.P1,NP.P2]>CD+1 Then Begin
            D[NP.P1,NP.P2]:=CD+1;
            Prev[NP.P1,NP.P2]:=P;
            Inc(QNum[N1]);
            Qu[N1,QNum[N1]]:=NP;
          End;
        End;
      End;
      For J:=1 To NE[P.P2] Do Begin
        NP:=P;
        NP.P2:=E[P.P2,J];
        If (G[NP.P1,NP.P2]>0) Then Begin
          If D[NP.P1,NP.P2]>CD+1 Then Begin
            D[NP.P1,NP.P2]:=CD+1;
            Prev[NP.P1,NP.P2]:=P;
            Inc(QNum[N1]);
            Qu[N1,QNum[N1]]:=NP;
          End;
        End;
      End;
      For J:=1 To NE[P.P1] Do
        For JJ:=1 To NE[P.P2] Do Begin
          NP:=P;
          NP.P1:=E[P.P1,J];
          NP.P2:=E[P.P2,JJ];
          If (G[NP.P1,NP.P2]>0) And ((NP.P1<>P.P2) Or (NP.P2<>P.P1) Or (G[NP.P1,NP.P2]>1)) Then Begin
            If D[NP.P1,NP.P2]>CD+2 Then Begin
              D[NP.P1,NP.P2]:=CD+2;
              Prev[NP.P1,NP.P2]:=P;
              Inc(QNum[N2]);
              Qu[N2,QNum[N2]]:=NP;
            End;
          End;
        End;
    End;
    QNum[C]:=0;
    C:=(C+1) Mod 3;
  End;
  NPath:=0;
  Otkat(T);
End;

Procedure Save;
Var
  I:Integer;
Begin
  ReWrite(Output,OutFile);
  WriteLn(D[T.P1,T.P2],' ',NPath);
  For I:=1 To NPath Do With Path[I] Do WriteLn(P1,' ',P2);
  Close(Output);
End;

begin
  Load;
  Solve;
  Save;
end.
 