Programacion Competitiva Bolivia

En una convención Hacker, llevada a cabo en las profundidades de la Amazonía boliviana, el hacker que tiene como nombre “El Gato”, te invitó a que lo acompañaras a un curso de Lock Picking.

Al final del curso, te muestran una caja fuerte. El que la pueda abrir, ganará uno de los premios del evento: El Pacú de Sombrero Negro

Ya que quieres hacer quedar mal a tu amigo, El Gato, te pones como desafío, ser el primero en abrir la caja fuerte en el menor número de movimientos.

Dicha caja fuerte, consiste en varios sistemas de engranajes, donde cada engranaje muestra una letra. Si puedes hacer que todos los engranajes muestren una misma letra, determinada por el fabricante, la caja fuerte se abrirá.

Un sistema de engranajes está compuesto por engranajes conectados.

Si un engranaje gira, todos los engranajes directamente conectados a este, girarán en el sentido contrario.

Si un engranaje es forzado a girar en ambas direcciones, este no girará y detendrá a todo el sistema de engranajes.

Un movimiento consiste en mover un engranaje a la izquierda o a la derecha.

Por ejemplo, en los siguientes 2 sistemas de engranajes tenemos que:

Sistema de engranajes a

Sistema de engranajes b

Rotaciones

En el sistema de engranajes (a) Si giramos el engranaje 1 a la derecha, el 2 se moverá a la izquierda, el 3 a la derecha y el 4 a la derecha.

Bloqueo

El sistema de engranajes (b), está bloqueado: Si giramos el engranaje 1 a la derecha, el engranaje 2 y 3 se moverán a la izquierda. PERO, el engranaje 2,al moverse a la izquierda, también está forzando a que el engranaje 3 se mueva a la derecha. Ya que un engranaje está siendo forzado en ambas direcciones, el sistema se bloquea.

• Cada engranaje, muestra una letra diferente, dependiendo de cuantas veces haya girado.
• Todos los engranajes contienen la misma cantidad de letras.
• Cada engranaje muestra una letra a la vez.
• Al mover un engranaje, se muestra la siguiente letra.

Por ejemplo:

Si las letras que muestra un engranaje son: a,b,c,d,e y el engranaje está mostrando actualmente la letra c.

Si el engranaje se mueve a la derecha , la siguiente letra en ser mostrada será d, después e en el segundo movimiento, después a y así sucesivamente.

Si el engranaje se mueve a la izquierda, la siguiente letra en ser mostrada será b, después a en el segundo movimiento, después e y así sucesivamente.

Entrada

La primera linea de la entrada contiene un numero entero que representa los casos de prueba. Cada caso de prueba contiene varias líneas tal y como se describe a continuación: 3 números N,K,L, el número de engranajes (1 ≤ N ≤ 1000),el número de letras que contiene cada engranaje y la letra determinada por el fabricante respectivamente. Seguidamente, se muestran N líneas, cada uno con K diferentes letras mayúsculas. Seguidamente, se muestran N líneas, cada una con una letra valida, la letra actual del engranaje i-esimo. Finalmente, un número M, el número de conexiones entre engranajes. Seguido de M lineas, cada una con 2 números diferentes a y b, definiendo una conexión entre los engranajes a y b. (1 ≤ a,b ≤ N).

Todas las letras son mayúsculas y pertenecen al alfabeto inglés.

Salida

Por cada caso de prueba, imprimir su respectivo número de caso y el mínimo número de movimientos para abrir la caja fuerte. Imprima -1 si no fuera posible abrir la caja fuerte.

+----------------------+--------------------+
| Ejemplos de entrada  | Ejemplos de salida |
+----------------------+--------------------+
| 4                    | Caso 1: 2          |
| 2 2 B                | Caso 2: 1          |
| A B                  | Caso 3: -1         |
| A B                  | Caso 4: 0          |
| A                    |                    |
| A                    |                    |
| 0                    |                    |
|                      |                    |
| 3 3 X                |                    |
| A B X                |                    |
| C X A                |                    |
| X A B                |                    |
| A                    |                    |
| C                    |                    |
| A                    |                    |
| 2                    |                    |
| 1 2                  |                    |
| 2 3                  |                    |
|                      |                    |
| 3 3 X                |                    |
| A B X                |                    |
| C X A                |                    |
| X A B                |                    |
| A                    |                    |
| C                    |                    |
| A                    |                    |
| 3                    |                    |
| 1 2                  |                    |
| 2 3                  |                    |
| 3 1                  |                    |
|                      |                    |
| 3 3 X                |                    |
| A B X                |                    |
| C X A                |                    |
| X A B                |                    |
| X                    |                    |
| X                    |                    |
| X                    |                    |
| 3                    |                    |
| 1 2                  |                    |
| 2 3                  |                    |
| 3 1                  |                    |
+----------------------+--------------------+

En el primer caso de ejemplo, basta con mover cada engranaje a la derecha, dando un total de 2 movimientos.

En el segundo caso de ejemplo, basta con mover el primer engranaje a la izquierda, dando un total de un movimiento.

En el tercer caso de ejemplo, los engranajes están bloqueados y no se encuentran en la letra determinada por el fabricante, la X

En el último caso de ejemplo, los engranajes están bloqueados pero todos se encuentran en la letra determinada por el fabricante, resultando en 0 movimientos para abrirla.