program kingdom;

{$APPTYPE CONSOLE}

var
	i, j, k	: integer;
	n, m		: integer;
   a1, b1	: integer;
   a2, b2	: integer;
   aa, bb	: integer;
   a			: array [1..100, 1..100] of record
   	n		: integer;
      a, b	: integer;
   	IsWay	: Boolean;
   end;
   nn			: integer;
   b			: array [1..10000] of record
   	a, b	: integer;
   end;
   NoCh		: Boolean;

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

   readln(n, m, a1, b1, a2, b2);

   for i := 1 to n do
   	for j := 1 to n do begin
      	a[i, j].n := 1000000;
      	a[i, j].IsWay := false;
      end;

   for i := 1 to m do begin
   	readln(j, k);
      a[j, k].IsWay := true;
      a[k, j].IsWay := true;
   end;

   a[a1, b1].n := 0;
   repeat
   	NoCh := true;
      for i := 1 to n do
      	for j := 1 to n do
         	if a[i, j].IsWay then begin
         		for aa := 1 to n do
               	if (aa <> i) and (aa <> j) and a[aa, j].IsWay and (a[i, j].n + 1 < a[aa, j].n) then begin
                  	a[aa, j].n := a[i, j].n + 1;
                     a[aa, j].a := i;
                     a[aa, j].b := j;
                     Noch := false;
	            	end;
         		for bb := 1 to n do
               	if (bb <> i) and (bb <> j) and a[i, bb].IsWay and (a[i, j].n + 1 < a[i, bb].n) then begin
                  	a[i, bb].n := a[i, j].n + 1;
                     a[i, bb].a := i;
                     a[i, bb].b := j;
                     Noch := false;
	            	end;
         		for aa := 1 to n do
	         		for bb := 1 to n do
                     if (aa <> i) and (bb <> j) and ((aa <> j) or (bb <> i)) and a[aa, bb].IsWay and (a[i, j].n + 2 < a[aa, bb].n) then begin
                        a[aa, bb].n := a[i, j].n + 2;
                        a[aa, bb].a := i;
                        a[aa, bb].b := j;
	                     Noch := false;
                     end;
         	end;
   until NoCh;
   nn := 0;
   aa := a2;
   bb := b2;
   repeat
   	nn := nn + 1;
   	b[nn].a := aa;
      b[nn].b := bb;
      a1 := aa;
      b1 := bb;
      aa := a[a1, b1].a;
      bb := a[a1, b1].b;
   until a[a1, b1].n = 0;
   writeln(a[a2, b2].n, ' ', nn);
   for i := nn downto 1 do
   	writeln(b[i].a, ' ', b[i].b);
end.
