program Kingdom;

{$APPTYPE CONSOLE}

uses
  SysUtils;

Var P,Ans       : array [1..2000,1..2] of longint;
    A           : array [1..2000,1..2000] of Longint;
    Nsm         : array [1..100] of longint;
    Sm          : array [1..100,1..100] of longint;
    Met,W,From  : array [1..2000] of longint;
    i,j,k,z,M,N : longint;
    a1,b1,a2,b2 : longint;

Function Nport(xA, xB : longint) : longint;
Var B,E,D : longint;
Begin
  B:=1; E:=2*M;
  While B<E do Begin
    D:=(B+E) div 2;
    If (P[D,1]<Xa) OR ((P[D,1]=Xa)AND(P[D,2]<xB)) then B:=D+1 Else E:=D;
  End;
  If (Xa=P[B,1])AND(xB=P[B,2]) then Nport:=B Else NPort:=0;
End;

begin
  { TODO -oUser -cConsole Main : Insert code here }
  assignFile(input,'kingdom.in'); reset(input);
  assignFile(output,'kingdom.out'); Rewrite(output);


  Fillchar(NSM, Sizeof(NSM), 0);
  Fillchar(A, Sizeof(A), 0);

  Readln(N,M,a1,b1,a2,b2);
  For i:=1 to M do Begin
    read(j,k);
    Inc(Nsm[j]); Inc(Nsm[k]);
    Sm[j,Nsm[j]]:=k; Sm[k,Nsm[k]]:=j;
    P[2*i-1,1]:=j; P[2*i-1,2]:=k;
    P[2*i,1]:=k; P[2*i,2]:=j;
  End;

  For i:=1 to 2*M do
  For j:=1 to 2*M-1 do
  If (P[j,1]>P[j+1,1])OR((P[j,1]=P[j+1,1])AND(P[j,2]>P[j+1,2])) then Begin
    k:=P[j,1]; P[j,1]:=P[j+1,1]; P[j+1,1]:=k;
    k:=P[j,2]; P[j,2]:=P[j+1,2]; P[j+1,2]:=k;
  End;

  For i:=1 to 2*M do Begin
    For j:=1 to Nsm[P[i,1]] do Begin
      k:=Nport(Sm[P[i,1],j],P[i,2]);
      if k<>0 then A[i,k]:=1;
    End;

    For j:=1 to Nsm[P[i,2]] do Begin
      k:=Nport(P[i,1],Sm[P[i,2],j]);
      if k<>0 then A[i,k]:=1;
    End;

    For j:=1 to Nsm[P[i,1]] do
    For k:=1 to Nsm[P[i,2]] do Begin
      z:=Nport(SM[P[i,1],j], SM[P[i,2],k]);
      If z<>0 then A[i,z]:=2;
    End;
  End;

  For i:=1 to 2*M do
  A[i,Nport(P[i,2],P[i,1])]:=0;

  Fillchar(Met, SizeOf(Met), 0);
 Fillchar(From, SizeOf(From), 0);
  Fillchar(W,sizeof(W), 0);
  Met[Nport(a1,b1)]:=1;
  For i:=1 to 2*M do W[i]:=1000000000;
  W[Nport(a1,b1)]:=0;

  While TRUE do Begin
    i:=0;
    For j:=1 to 2*M do
    If Met[j]=1 then Begin
      If i=0 then i:=j
      Else Begin
        If W[j]<W[i] then i:=j;
      End;
    End;
    if i=0 then Break;

    For j:=1 to 2*M do
    If A[i,j]<>0 then
      If W[j]>W[i]+A[i,j] then Begin
        From[j]:=i;
        W[j]:=W[i]+A[i,j];
        Met[j]:=1;
      End;
    Met[i]:=2;
  End;

  z:=Nport(a2,b2);
  Write(W[z],' ');
  k:=0;
  While z<>0 do Begin
    Inc(k);
    Ans[k,1]:=P[Z,1];
    Ans[k,2]:=P[Z,2];
    z:=From[z];
  End;

  Writeln(k);
  For i:=k downto 1 do Writeln(Ans[i,1],' ',Ans[i,2]);

  close(input);
  close(output);
end.
