Problem E
Word Ladders

The graph created from the sample input.

We would like to know how similar words are to other words. The metric we use is how far apart two words are in a graph. We define a directed graph of five letter words as follows. There is one node for every word in a given dictionary. There is an arc from $v$ to $w$ if each of the last four letters of $v$ appears in $w$. For example, there is an arc from yodel to lodes, but not from lodes to yodel because the latter contains no S. On the other hand, there is an arc from sharp to graph and back. All four letters have to appear with repetitions, so there is an arc from where to ether (both Es appear) but not to retch (E appears only once).

Input

The first line contains integers $N$ and $Q$, such that $10 \leq N \leq 50\, 000$ and $1 \leq Q \leq 10$. Then follows $N$ five letter words. This is the word list that defines our graph. After follows $Q$ lines, each containing a query. Each query consists of two space separated words, that both are in the word list. Each word consists of exactly five lowercase letters (a–z).

Output

For each of the $Q$ queries, output a line containing one integer, the distance from the first word to the second word in the graph. If the second word is not reachable from the first word, output $-1$.

10 6
there
which
their
about
these
words
would
other
write
could
other there
other their
could would
would could
there other
about there

1
1
1
1
-1
-1