Primeiro, coloque as m meninas em uma fila. Dá m! possibilidades. Depois, os m meninos em outra fila. Dá m! possibilidades. Depois, escolha se a fila vai começar com um menino ou menina. 2 possibilidades. E entrelace as duas filas.
Dá um total de 2*(m!)^2.
Só precisa agora cuidar das permutacoes ciclicas disto tudo... Creio que dividir por 2m funcione, mas tenho que testar...