# Word Ladders

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$.

Sample Input 1 | Sample 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 |