CF49E.Common ancestor

The DNA sequence for every living creature in Berland can be represented as a non-empty line consisting of lowercase Latin letters. Berland scientists found out that all the creatures evolve by stages. During one stage exactly one symbol of the DNA line is replaced by exactly two other ones. At that overall there are n permissible substitutions. The substitution a__i->b__i__c__i means that any one symbol a__i can be replaced with two symbols b__i__c__i. Every substitution could happen an unlimited number of times.

They say that two creatures with DNA sequences _s_1 and _s_2 can have a common ancestor if there exists such a DNA sequence _s_3 that throughout evolution it can result in _s_1 and _s_2, perhaps after a different number of stages. Your task is to find out by the given _s_1 and _s_2 whether the creatures possessing such DNA sequences can have a common ancestor. If the answer is positive, you have to find the length of the shortest sequence of the common ancestor’s DNA.

贝兰德（Berland）中每种生物的 DNA 序列均可表示为一个非空的、仅由小写拉丁字母组成的字符串。贝兰德科学家发现，所有生物均通过若干阶段演化而来。在每个演化阶段中，DNA 字符串中的恰好一个字符被恰好两个字符所替换。总共存在 $n$ 种允许的替换规则。替换规则 $a_i \to b_i c_i$ 表示：任意一个字符 $a_i$ 均可被替换为两个字符 $b_i c_i$。每种替换规则均可被使用任意多次。

若存在某个 DNA 序列 $s_3$，使得经过若干演化阶段（可能阶段数不同）后，$s_3$ 可分别演化为 $s_1$ 和 $s_2$，则称具有 DNA 序列 $s_1$ 和 $s_2$ 的两种生物拥有共同祖先。你的任务是：给定 $s_1$ 和 $s_2$，判断它们是否可能拥有共同祖先；若答案为肯定，则还需找出该共同祖先 DNA 序列的最短长度。

The first line contains a non-empty DNA sequence _s_1, the second line contains a non-empty DNA sequence _s_2. The lengths of these lines do not exceed 50, the lines contain only lowercase Latin letters. The third line contains an integer n (0 ≤ n ≤ 50) — the number of permissible substitutions. Then follow n lines each of which describes a substitution in the format a__i->b__i__c__i. The characters a__i, b__i, and c__i are lowercase Latin letters. Lines _s_1 and _s_2 can coincide, the list of substitutions can contain similar substitutions.

第一行包含一个非空的 DNA 序列 $s_1$，第二行包含一个非空的 DNA 序列 $s_2$。这两行的长度均不超过 50，且仅包含小写拉丁字母。第三行包含一个整数 $n$（$0 \le n \le 50$）—— 表示允许的替换操作次数。随后是 $n$ 行，每行描述一次替换操作，格式为 $a_i\rightarrow b_i c_i$。其中字符 $a_i$、$b_i$ 和 $c_i$ 均为小写拉丁字母。序列 $s_1$ 和 $s_2$ 可以相同，替换操作列表中也可能包含重复的替换操作。

If _s_1 and _s_2 cannot have a common ancestor, print -1. Otherwise print the length of the shortest sequence _s_3, from which _s_1 and _s_2 could have evolved.

如果 $s_1$ 和 $s_2$ 不存在共同祖先，则输出 -1；否则输出最短序列 $s_3$ 的长度，使得 $s_1$ 和 $s_2$ 均可由 $s_3$ 演化而来。