A palidrome craftsperson starts to work in the early morning, with the clear air allowing him to polish up his palindromes.

On this morning, he is making his pieces to submit to the International Contest for Palindrome Craftspeople.

By the way, in order to make palindromes, he uses a special dictionary which contains a set of words and a set of ordered pairs of the words. Any words and any ordered pairs of consecutive words in his palindromes must appear in the dictionary.

We already have his dictionary, so let's estimate how long a palindrome he can make.

The first line in the data set consists of two integers `N` (`1 \leq N \leq 100`) and `M` (`0 \leq M \leq 1\,000`).
`N` describes the number of words in the dictionary and `M` describes the number of ordered pairs of words.

The following `N` lines describe the words he can use.
The `i`-th line (`1`-based) contains the word `i`, which consists of only lower-case letters and whose length is between `1` and `10`, inclusive.

The following `M` lines describe the ordered pairs of consecutive words he can use.
The `j`-th line (`1`-based) contains two integers `X_j` and `Y_j` (`1 \leq X_j, Y_j \leq N`).
`X_j` describes the (`1`-based) index of the former word in the palindrome and `Y_j` describes that of the latter word.

Print the maximal length of the possible palindrome in a line. If he can make no palidromes, print "0". If he can make arbitrary long palindromes, print "-1".

2 2 ab ba 1 1 1 2

4

2 2 ab ba 1 1 2 2

0

2 2 ab a 1 1 1 2

-1

Source: ACM-ICPC Japan Alumni Group Summer Camp 2011
, Day 3, Tokyo, Japan, 2011-09-19

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/