Transformers P84831

Tenemos una secuencia de robots de dos tipos distintos (¿a¿ y ¿b¿), dispuestos en fila. A cada instante, una subsecuencia consecutiva de esos robots puede ser transformada en otra secuencia de robots mas grande (los motivos por los que esto pasa son misteriosos, y no entraremos en este detalle).

Se os da una secuencia origen y una secuencia objetivo, y las reglas que os permiten transformar subsecuencias de robots. Por ejemplo, a partir de las reglas

y de la secuencia original ¿aab¿, se pueden hacer (entre otras) las transformaciones sucesivas

Se os pide hacer un programa que, dadas la secuencia original y final, y las reglas de transformación, calcule el minimo número de pasos necesarios para transformar la secuencia original en la secuencia objetivo. Si no es posible conseguirlo, debe indicarse. Todas las reglas dadas provocarán un incremento del numero de robots en la secuencia.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con la secuencia origen y la secuencia objetivo, seguidas de un natural n, seguido de n reglas de transformación, cada una definida con sus dos secuencias, formadas exclusivamente por las letras ¿a¿ y ¿b¿. La segunda secuencia de cada regla será más larga que la primera.

Salida

Para cada caso de la entrada, tenéis que escribir el número de caso, seguido del mínimo número de pasos necesarios para pasar de la secuencia original a la secuencia objetivo. Si no es posible, debe indicarse. Seguid el formato de los ejemplos.

Puntuación

• Test1:  ‍40 Puntos ‍

  Resolver casos de prueba como los del ejemplo 1, donde todos los casos tienen solución, y siempre en 3 pasos o menos.

• Test2:  ‍60 Puntos ‍

  Resolver casos de prueba con solución de hasta 9 pasos, y también casos sin solución, como los del ejemplo 2.