Este cuento relata la historia del joven Teseo, hijo de Egeo rey de Atenas, que tuvo que enfrentarse al minotauro malvado del laberinto de Cnossos, situado en la isla de Creta. La historia narra lo siguiente:

El rey de Atenas estaba obligado a entregar anualmente un tributo de catorce jóvenes, siete de cada sexo, a su homólogo de Creta. Los catorce jóvenes eran destinado al alimento del Minotauro, un monstruo mitad hombre mitad toro que habitaba en el laberinto construido por Dédalo, habilísimo arquitecto y escultor.

Teseo, hijo de Egeo, rey de Atenas, se presenta voluntario para ir a Creta como uno de los catorce jóvenes del tributo anual, con la declarada intención de matar al Minotauro y liberar a su patria del odioso tributo. Al llegar a Creta se enamora de la princesa Ariadna, hija del rey Minos, y esta le proporciona los medios para matar al Minotauro, así como un ovillo de hilo con el que poder encontrar el camino de regreso dentro del laberinto.

Teseo escoge una entrada del laberinto seguido atará un extremo el hilo a la puerta de la entrada e irá en busca del Minotauro y de los jovenes Tributos. dentro del laberinto solo se puede mover en cuatro direcciones (este, oeste, norte, sur). Para avanzar de un punto a otro se utiliza 1 [diploun bema] de hilo.

En todo momento Teseo puede decidir si continuar recorriendo el laberinto o volver a la entrada por la cual ingreso, si desea volver recogera el hilo en el camino de vuelta.

Dado un laberinto se pide:
Verificar si Teseo mató Minotauro.
Calcular cuantos Tributos no pudieron ser rescatados.
Calcular la longitud mínima de hilo que se usa para realizar la mision.

La entrada consiste en un solo caso de prueba. La primera linea contiene dos enteros N y M que representan las dimensiones de laberinto, acontinuacion el laberinto que solo contiene los caracteres:
'#': Representa un Muro.
'.': Representa un espacio libre por donde moverse.
'M': Representa al Minotauro a su vez un espacio libre por donde moverse.
'T': Representa un Tributo a su vez un espacio libre por donde moverse.

Considere como entradas al laberinto los bordes del laberinto (este, oeste, norte, sur) que tengan un espacio libre.

2<=N<=100
2<=M<=100
número de tributos <= N*M
nùmero de entradas <= 2*N+2*M-4

La salida consiste en tres lineas.
En la primera linea, imprimir "Minotauro is dead" si Teseo mató Minotauro, caso contrario imprimir "Minotauro is alive".
En la segunda linea, imprimir "Tributes lossed" seguido del número de Tributos que Teseo no pudo rescatar.
En la tercera linea, imprimir "Lenght" seguido de la longitud mínima de hilo que uso Teseo para realizar las tareas anteriores.

Teseo mata al Minotauro y regresa vencedor a Atenas, llevándose consigo a Ariadna. El barco hace escala en la isla de Naxos. Ariadna se queda dormida en la playa, y ese es el momento que elige Minerva para ordenarle al héroe que leve anclas y siga sin demora camino del Ática. Cumple la orden Teseo, y Ariadna despierta y queda desconsolada viendo cómo se aleja el barco de su amado. Con escasas variantes, cuya insignificancia excusa su relato, así se nos ha transmitido ésta emocionante historia.

Competencia Interna Segunda Division ICPC-UMSA