F - Frases palíndromos

Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Fito es un fanático de los palíndromos, las palabras que se leen igual de izquierda a derecha que de derecha a izquierda. Recientemente él está investigando sobre algunas frases que son palíndromos. Una frase es una lista de palabras, y es palíndromo si al concatenar todas las palabras, omitiendo los espacios, la palabra que se forma es palíndromo.

Por ejemplo: “ anita lava la tina ” es una frase palíndromo, porque la palabra " anitalavalatina " es palíndromo.

Para su investigación Fito necesita buscar una frase palíndromo interesante, sea conocida o no, así que para apoyarse buscó un diccionario. El diccionario contiene una lista de palabras que son las que él puede usar y una lista de pares de esas palabras, que lo van a ayudar a formar la frase. Cada par indica que las palabras que lo forman pueden aparecer consecutivas en la frase, y además, todo par de palabras consecutivas en la frase debe aparecer en la lista. Las palabras se pueden utilizar más de una vez.

Fito quiere que lo ayuden a encontrar la frase palindromo más grande que se puede construir con el diccionario que encontró.

Input

Línea 1 : La primera línea de la entrada contiene dos enteros $N$ $(1 \leq N \leq 100)$ y $M$ $(0 \leq M \leq 1000)$ separados por espacio, que representan la cantidad de palabras y la cantidad de pares que contiene el diccionario respectivamente.
Línea 2...N+1 : La $i+1$-ésima línea contendrá la $i$-ésima palabra (c ada palabra estará compuesta por al menos $1$ y a lo sumo $10$ letras del alfabeto inglés).
Linea N+2 ... N+M+1 : Un par de índices por línea $a$ y $b$ $(1 \leq a, b \leq N)$ separados por un espacio en blanco.

Output

Línea 1 : La longitud de la frase palíndromo más larga que Fito puede formar. Si Fito no puede formar ninguna palabra palíndromo se debe imprimir $0$ y si Fito puede construir frases palíndromos arbitrariamente largas se debe imprimir $-1$.

Sample test(s)

Input
4 3 anita lava la tina 1 2 2 3 3 4
Output
15
Input
2 2 ab ba 1 1 2 2
Output
0
Input
2 2 ab a 1 1 1 2
Output
-1