← 返回题目列表

Codeforces · 49/E

E. 共同祖先

中文机器翻译题面 查看原题

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