题目描述:
邪神洛基偷走了宇宙魔方,美国队长要夺回它。他发现宇宙魔方被锁在了一个特制的密码箱中,密码箱上目前显示着一串文字(字符串a)。钢铁侠帮助美国队长破解了密码箱的操作方式:每次可以按照规则把一个字母转换为另一个字母。绿巨人浩克把洛基摔了又摔,洛基不得已说出了正确的密码(字符串b)。请你帮助美国队长计算他最少需要操作多少次才能打开密码箱,夺回宇宙魔方。
输入格式:
第一行输入字符串a,长度不大于 10001000,只包含小写字母,表示密码箱上的初始文字。
第二行输入字符串b,只包含小写字母,保证长度和第一个字符串相等,表示正确密码。
第三行输入一个整数 n(0 \le n \le 676)n(0≤n≤676)。
接下来 nn 行,每行输入两个空格隔开的字符 X i, Y i,表示操作规则:一次操作能把一个字符 X i变换成字符 Y i。
输出格式:
如果密码箱能被打开,输出最少的操作次数。否则输出 -1。
样例输入:
dabc
dddd
3
a b
b c
c d
样例输出:
6