Matcom Online Grader
II Copa UHEnded |
F - Frases palíndromos
Languages: C, C++, Java, Pascal, Haskell, 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.