1046: 变形课的烦恼

霍格沃茨魔法学院是欧洲最为著名的魔法学院，它位于英格兰北部安尼克山湖旁的城堡中。霍格沃茨魔法学院的办学目标是为欧洲大陆培养合格的魔法师。

学校的课程琳琅满目，有魔药课（Potion）、占卜课（Divination）、魔咒课（Charms）、变形课（Transfiguration）、黑魔法防御术（Defence Against the Dark Arts）、麻瓜研究（Muggle Studies）等等。而其中最为重要的，当属变形课（Transfiguration），也就是将一件物品变成另一件物品的神奇法术。

SYH对魔法有着强烈的兴趣。这个暑假，SYH决定离家出走，到霍格沃茨魔法学院进行短期学习。然而他在变形课上遇到了大麻烦。我们都知道，施放法术需要魔法师念出咒语。而这些咒语通常非常长而且绕口，有时甚至会达到几百个字符。SYH的记忆力非常差，他经常会因为记错咒语，从而将他的晚餐面包变成棒球。

不过SYH在学习的过程中发现了一个规律：如果咒语是以a字符开头b字符结尾的一个单词，那么它的作用就是将物体a变成物体b。

现在SYH有一本非常厚的咒语词典，其中包含N条咒语（其中每条咒语一定是由26个小写英文字符所组成的）。现在SYH想要知道，将A物品变成B物品是否可行，如果可行，最少需要念几次咒语？

输入文件名为 magic.in。

输入共N+Q+1行：第一行为2个正整数N、Q，分别代表字典中咒语的条数和询问个数。

       接下来N行，每行有一个字符串（仅包含26个小写英文字符），描述字典里的一条咒语。

       接下来Q行，每行有两个小写英文字符a、b，用空格分隔，表示询问a物品变为b物品最少要念多少次咒语。

输出文件名为 magic.out。

输出共有Q行，每一行有一个整数，针对各个询问，依次输出念咒语的最少次数。如果a物品无法变为b物品，输出-1。

9 4
so
soon
river
goes
them
got
moon
begin
big
b m
b n
s r
n n

3
1
-1
0