program taskK_EX2;
{$APPTYPE CONSOLE}
const
   MAX1 = 110;
   MAX2 = 2100;
   INF = 30000;

var
   fi,fo: TextFile;
   ax: array [1..MAX1,1..MAX1] of byte;
   i1,i2,n,m,a1,b1,a2,b2,bf1,bf2: longint;
   ay: array [1..MAX2,1..MAX2] of byte;
   aL,aP: array [1..MAX2] of smallint;
   V: array [1..MAX2,1..2] of longint;
   VCnt: longint;
   St,Fn,Crr: longint;

   W: array [1..MAX2] of smallint;
   WCnt: longint;

   ConstL: array [1..MAX2] of byte;
   MinV: longint;

begin
   AssignFile(fi,'kingdom.in');
   AssignFile(fo,'kingdom.out');
   Rewrite(fo);
   Reset(fi);
   //input
   VCnt:=0;
   Read(fi,n,m,a1,b1,a2,b2);
   for i1:=1 to m do
      begin
         Read(fi,bf1,bf2);
         ax[bf1,bf2]:=1;
         ax[bf2,bf1]:=1;
         //add vrx
         inc(VCnt);
         V[VCnt,1]:=bf1;
         V[VCnt,2]:=bf2;
         inc(VCnt);
         V[VCnt,1]:=bf2;
         V[VCnt,2]:=bf1;
      end;
   for i1:=1 to n do ax[i1,i1]:=1;
   //build adv gr
   for i1:=1 to VCnt-1 do for i2:=i1+1 to VCnt do
      begin
         //check
         if (ax[V[i1,1],V[i2,1]]=1) AND (ax[V[i1,2],V[i2,2]]=1) AND NOT ((V[i1,1]=V[i2,2]) AND (V[i1,2]=V[i2,1])) then
            begin
               if (V[i1,1]=V[i2,1]) OR (V[i1,2]=V[i2,2]) then
                  begin
                     ay[i1,i2]:=1;
                     ay[i2,i1]:=1;
                  end
               else
                  begin
                     ay[i1,i2]:=2;
                     ay[i2,i1]:=2;
                  end
            end;
      end;
   //find st and fn
   for i1:=1 to VCnt do
      begin
         if (V[i1,1]=a1) AND (V[i1,2]=b1) then St:=i1;
         if (V[i1,1]=a2) AND (V[i1,2]=b2) then Fn:=i1;
      end;
   //init
   for i1:=1 to MAX2 do
      begin
         aL[i1]:=INF;
         aP[i1]:=0;
      end;
   aL[St]:=0;
   //dijxtra
   //ConstL[St]:=1; Crr:=St;
   while ConstL[Fn]=0 do
      begin
         MinV:=0;
         for i1:=1 to VCnt do if (ConstL[i1]=0) AND ((MinV=0) OR (aL[i1]<aL[MinV])) then MinV:=i1;
         //wave
         ConstL[MinV]:=1;
         for i1:=1 to VCnt do if (ConstL[i1]=0) AND (aY[MinV,i1]>0) AND (aL[MinV]+aY[MinV,i1]<aL[i1]) then
            begin
               aL[i1]:=aL[MinV]+aY[MinV,i1];
               aP[i1]:=MinV;
            end;
      end;
   //reverse
   Crr:=Fn; WCnt:=0;
   while Crr<>0 do
      begin
         //add to way
         inc(WCnt);
         W[WCnt]:=Crr;
         //next
         Crr:=aP[Crr];
      end;
   //output
   Writeln(fo,aL[Fn],' ',WCnt);
   for i1:=WCnt downto 1 do Writeln(fo,V[W[i1],1],' ',V[W[i1],2]);
   //deinit
   Close(fo);
   Close(fi);
end.
