program Project1;

{$APPTYPE CONSOLE}
type
   TSite=record
      x,y:integer;
   end;

var N,M,i,j,k,x,y:integer;
    graf:array[1..100,1..100] of boolean;
    obr:array[1..100,1..100] of TSite;
    S1,S2,F1,F2:integer;
    queue:array[1..1000000] of TSite;
    q_b,q_e:integer;
    elm,zz:TSite;

procedure push(a:TSite);
begin
   inc(q_e);
   queue[q_e]:=a;
end;

procedure pop(var a:TSite);
begin
   inc(q_b);
   a:=queue[q_b];
end;

begin
   assign(input,'kingdom.in');
   reset(input);
   assign(output,'kingdom.out');
   rewrite(output);

   read(N,M,S1,S2,F1,F2);

   for i:=1 to M do begin
      read(x,y);
      graf[x,y]:=true;
      graf[y,x]:=true;
   end;
   q_b:=0;
   q_e:=0;
   elm.x:=S1;
   elm.y:=S2;
   push(elm);
   obr[S1,S2].x:=-1;
   obr[S1,S2].y:=-1;
   while q_b<>q_e do begin
      pop(zz);
      if (zz.x=F1) and (zz.y=F2) then break;

         for j:=1 to N do
            if (obr[zz.x,j].x=0) and
               (graf[zz.y,j]) and (graf[zz.x,j]) then begin

               elm.x:=zz.x;
               elm.y:=j;
               push(elm);
               obr[elm.x,elm.y]:=zz;
            end;

         for j:=1 to N do
            if (obr[j,zz.y].x=0) and
               (graf[j,zz.x]) and (graf[j,zz.y]) then begin

               elm.x:=j;
               elm.y:=zz.y;
               push(elm);
               obr[elm.x,elm.y]:=zz;
            end;

      for i:=1 to N do
         for j:=1 to N do
            if (obr[i,j].x=0) and (graf[zz.x,i]) and
               (graf[zz.y,j]) and (graf[i,j]) and ((zz.x<>j)or(zz.y<>i)) then begin

               elm.x:=i;
               elm.y:=j;
               push(elm);
               obr[elm.x,elm.y]:=zz;
            end;
            
   end;

   if (zz.x=F1) and (zz.y=F2) then begin
      i:=0;
      x:=0;
      while zz.x<>-1 do begin
         inc(i);
         queue[i]:=zz;
         if obr[zz.x,zz.y].x<>-1 then begin
            if (zz.x<>obr[zz.x,zz.y].x)and(zz.y<>obr[zz.x,zz.y].y) then inc(x,2)
            else inc(x);
         end;
         zz:=obr[zz.x,zz.y];
      end;
      writeln(x,' ',i);
      for j:=i downto 1 do writeln(queue[j].x,' ',queue[j].y);
   end;

end.

{
4 5 1 2 2 1
1 2
2 3
3 4
4 1
1 3

7 11 1 4 7 5
1 2
1 3
1 4
2 3
2 4
2 6
3 7
4 5
5 6
5 7
6 7

8 11 1 2 7 8
1 2
1 3
2 4
2 5
2 6
3 4
4 5
4 8
6 7
6 8
7 8

}