题目描述

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$ 的序列长度。

ababa
aba
2
c->ba
c->cc

2

ababa
aba
7
c->ba
c->cc
e->ab
z->ea
b->ba
d->dd
d->ab

1

ababa
aba
1
c->ba

-1