program Project1;

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

   ptelement=^Telement;

   Telement=record
      qq:TSite;
      Next:ptelement;
   end;

   ptnode=^tnode;
   TNode=record
      prior:integer;
      Left,Right:ptnode;
      List:ptElement;
   end;

var N,M,i,j,k,x,y,w: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;
    mark:array[1..100,1..100] of boolean;
    q_b,q_e:integer;
    elm,zz:TSite;
    root:ptnode;


procedure push(a:TSite;prior:integer);
var nw,cur,cur1:ptnode;
    nwe,cc:ptelement;
begin
   new(nwe);
   nwe^.qq:=a;
   nwe^.Next:=nil;

   cur1:=nil;
   cur:=root;
   while cur<>nil do begin
      cur1:=cur;
      if cur^.prior>prior then cur:=cur^.Left
      else if cur^.prior<prior then cur:=cur^.Right
      else begin
         cc:=cur^.List;
         while cc^.Next<>nil do cc:=cc^.Next;
         cc^.Next:=nwe;
         exit;
      end;
   end;

   new(nw);
   nw^.prior:=prior;
   nw^.Left:=nil;
   nw^.Right:=nil;
   nw^.List:=nwe;

   if cur1=nil then root:=nw
   else begin
      if cur1^.prior>prior then cur1^.Left:=nw
      else if cur1^.prior<prior then cur1^.Right:=nw;
   end;
end;

procedure pop(var a:TSite;var prior:integer);
var nw,cur,cur1:ptnode;
    nwe,cc,cc1:ptelement;
begin

   cur:=root;
   cur1:=nil;
   while cur^.Left<>nil do begin
      cur1:=cur;
      cur:=cur^.Left;
   end;

   prior:=cur^.prior;
   a:=cur^.List^.qq;

   cc:=cur^.List;
   cur^.List:=cur^.List^.Next;
   dispose(cc);

   if cur^.List=nil then begin
      //dispose(cur^.List);
      //cur^.List:=nil;

      if cur1=nil then begin
         cur1:=root.Right;
         dispose(root);
         root:=cur1;
      end else begin
         dispose(cur1^.Left);
         cur1^.Left:=nil;
      end;
   end;

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,0);
   obr[S1,S2].x:=-1;
   obr[S1,S2].y:=-1;
   mark[S1,S2]:=true;

   while root<>nil do begin
      pop(zz,w);

      //writeln(zz.x,' ',zz.y,' ',w);

      if (zz.x=F1) and (zz.y=F2) then break;

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

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

               mark[elm.x,elm.y]:=true;
            end;

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

               elm.x:=j;
               elm.y:=zz.y;
               push(elm,w+1);
               obr[elm.x,elm.y]:=zz;
               mark[elm.x,elm.y]:=true;
            end;

      for i:=1 to N do
         for j:=1 to N do
            if (not mark[i,j]) 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,w+2);
               obr[elm.x,elm.y]:=zz;
               mark[elm.x,elm.y]:=true;
            end;

   end;

   if (zz.x=F1) and (zz.y=F2) then begin
      //zz.x:=F1;
      //zz.y:=F2;
      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

}