Berland 中每种生物的 DNA 序列都可以表示为由小写拉丁字母组成的非空行。伯兰德科学家发现所有生物都是分阶段进化的。在一个阶段中,DNA 线中的一个符号恰好被另外两个符号所取代。总共有 n 种允许的替换。替换ai->bici 意味着任意一个符号ai 可以被两个符号bici 替代。每次替换都可以发生无限次。
他们说,如果存在这样的 DNA 序列 s3,并且在整个进化过程中可能会经过不同数量的阶段,可能会导致 s1 和 s2,那么具有 DNA 序列 s1 和 s2 的两个生物可以有一个共同的祖先。你的任务是根据给定的 s1 和 s2 找出拥有这种 DNA 序列的生物是否可以有一个共同的祖先。如果答案是肯定的,你必须找到共同祖先 DNA 的最短序列的长度。
输入
第一行包含非空DNA序列s1,第二行包含非空DNA序列s2。这些行的长度不超过 50,行仅包含小写拉丁字母。第三行包含一个整数 n (0 ≤ n ≤ 50) — 允许的替换数。然后接下来的 n 行每行都描述了 ai->bici 格式的替换。字符 ai、bi 和 ci 是小写拉丁字母。行 s1 和 s2 可以重合,替换列表可以包含类似的替换。
输出
如果 s1 和 s2 不能有共同的祖先,则打印 -1。否则打印最短序列 s3 的长度,s1 和 s2 可以从该序列演化而来。
示例
输入 #1
ababa aba 2 c->ba c->cc
输出 #1
2
输入 #2
ababa aba 7 c->ba c->cc e->ab z->ea b->ba d->dd d->ab
输出 #2
1
输入 #3
ababa aba 1 c->ba
输出 #3
-1