CF49E Common ancestor

Berland的每一个生物的DNA序列可以被表示成一个由小写字母组成的非空字符串。Berland的科学家们发现所有生物都是一步一步进化来的。在其中的每一步，DNA序列的一个字符会被替换成另外的两个。总共有$n$种允许的变化。变化$a_i\rightarrow b_ic_i$表示一个字符$a_i$可以被替换成两个字符$b_ic_i$。每一种变化均可以无限次发生。 科学家们表示，如果一个DNA序列$s_3$在整个进化过程中可以最终变为$s_1$和$s_2$，或许是经过了不同的步骤数，那么DNA序列分别为$s_1$和$s_2$的两个生物就会有一个共同祖先。现在给出$s_1$和$s_2$，你的任务是弄清楚分别拥有这两种DNA序列的生物是否有共同祖先。如果存在，你需要找出所有共同祖先中长度最短的DNA序列。

第一、二行分别包含一个非空字符串，即$s_1$和$s_2$。这两个字符串长度不超过50且只包含小写字母。第三行包含一个整数$n$，$0\leq n\leq50$，表示变化的种类数。随后的$n$行，每一行描述了一个变化形式$a_i\rightarrow b_ic_i$。$a_i$、$b_i$和$c_i$都是小写字母。$s_1$和$s_2$可能相同，给出的变化中可能包含有相似的变化。

如果$s_1$和$s_2$没有共同祖先，输出-1。否则输出最短的共同祖先$s_3$的序列长度。