A la fase final de l’edició Programame de l’any 2016, l’equip Rest in Python, composat per Kevin López, Eduard Pedrosa i Juan Quispe, van resoldre aquest problema en els primers 11 minuts del concurs. Per fer-ho, van haver de triar-lo entre els deu problemas del quadernet, i el van resoldre correctament en Java. Van guanyar el premi a l’equip més ràpid del concurs. Serveixi això per fer-lis un petit homenatge i animar-vos a vosaltres a resoldre correctament el problema.

El caos más absoluto se ha apoderado de la caja en la que se guardan los cables USB en el taller de hardware. La situación es ya insostenible, así que toca ordenarlos un poco. Como la tarea es pesada, se te ha ocurrido un juego: intentar conectar todos los cables unos con otros formando un gran círculo… aunque ni siquiera tienes claro que eso pueda hacerse, porque depende de cuántos cables de cada tipo haya en la caja…

Entrada

La entrada comienza con una línea con el número de casos de prueba que vendrán a continuación. Cada uno de los casos representa un escenario en el que hay que intentar conectar todos los cables. Contiene dos líneas, una con el número de cables que hay en la caja (al menos uno y no más de 10.000) y otra con una descripción de cada cable. Esa descripción no es más que dos letras, una por cada extremo, donde M significa conector USB macho y H conector hembra.

Sortida

Para cada caso de prueba hay que escribir POSIBLE si pueden conectarse todos los cables para formar un círculo o IMPOSIBLE en caso contrario.

Exemple d'Entrada

4
1
HM
1
HH
2
HM MH
3
HM HH MM

Exemple de Sortida

POSIBLE
IMPOSIBLE
POSIBLE
POSIBLE