Palabras crecientes P20520

Se os da una palabra origen y una palabra objetivo. Adicionalmente, tenéis unas cuantas reglas que os permiten transformar trozos de la palabra original. Por ejemplo, a partir de las reglas

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

Se os pide hacer un programa que, dadas las palabras original y final, y las reglas de transformación, calcule el mínimo número de pasos necesarios para transformar la palabra original en la palabra objetivo. Si no es posible conseguirlo, debe indicarse. Todas las reglas dadas provocarán un incremento en el tamaño de la palabra.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con la palabra origen y la palabra objetivo (ambas de longitud menor que 20), seguidas de un natural positivo $n\leq 12$, seguido de $n$ reglas de transformación, cada una definida con sus dos palabras (ambas de longitud menor que 10), formadas exclusivamente por las letras a y b. La segunda palabra 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 palabra original a la palabra objetivo. Si no es posible, debe indicarse. Seguid el formato de los ejemplos.

Puntuación

• Test-1:

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

• Test-2:

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