Problem C: PIPI的魔咒

Problem C: PIPI的魔咒

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 95  Solved: 32
[Submit] [Status] [Web Board] [Creator:]

Description

大魔术师PIPI有N个转换魔咒,每个转换魔咒可以将一个字符串变成另一个字符串。
比如说:
"PIPI"->"POPO"
"boy"->"girl"
"boy"->"u"
"isau"->"OJ"
那么对于字符串"PIPIisaboy",大魔术师PIPI可以通过2次魔咒将"PIPIisaboy"变成"POPOisagirl"。
也可以通过2次魔咒将"PIPIisaboy"变成"PIPIOJ"。

现在你知道了PIPI的所有魔咒,想让他把字符串A变成字符串B,请输出变换所需的最少步数。

Input

输入包含单组测试样例。
第一行输入字符串A和字符串B。1≤|A|,|B|≤30。
接下来输入一个数字N,代表转换魔咒的个数(1≤N≤10)。
接下来N行,每一行输入一个转换规则 X Y,代表可以将字符串X转化为Y。 1≤|X|,|Y|≤30
本题给出的所有字符串均不包含空格。

Output

如果在10次之内能将A变为B,输出从字符串A变为字符串B的最少次数。否则输出-1。

Sample Input

PIPIisaboy POPOisagirl
4
PIPI POPO
boy girl
boy u
isau OJ

Sample Output

2