Espècies incompatibles P37197

Considereu $n$ espècies diferents. Algunes poden ser incompatibles, en el sentit que s’han de mantenir separades. Per exemple, si les espècies fossin humà, lleó, goril·la, búfal i antílop, llavors la llista d’incompatibilitats podria ser: no es pot posar un humà al costat d’un lleó, ni un humà al costat d’un búfal, ni un lleó al costat d’un búfal, ni un lleó al costat d’un antílop.

Feu un programa que llegeixi les incompatibilitats entre espècies, i que escrigui totes les maneres de posar en fila un individu de cada espècie, de manera que no hi hagi dues espècies incompatibles una al costat de l’altra.

Entrada

L’entrada comença amb un nombre $n$ entre 1 i 52, seguit de $n$ lletres, cadascuna identificant una espècie diferent. A continuació ve un nombre $m$, seguit de $m$ parells diferents de lletres, cadascun indicant una incompatibilitat entre dues de les $n$ espècies.

El primer exemple d’entrada es correspon a l’exemple explicat anteriorment. “HL” vol dir que no es pot posar un humà al costat d’un lleó, etcètera. Fixeu-vos que “LH” voldria dir exactament el mateix.

Sortida

Escriviu totes les maneres de posar $n$ individus en fila, un de cada espècie, de manera que no n’hi hagi d’incompatibles que estiguin junts.

Informació sobre el corrector

Podeu escriure les solucions d’aquest exercici en qualsevol ordre.