190. 字串变换

已知有两个字串 $A$, $B$ 及一组字串变换的规则(至多 $6$ 个规则):

$A_1 \to B_1$

$A_2 \to B_2$

规则的含义为:在 $A$ 中的子串 $A_1$ 可以变换为 $B_1$、$A_2$ 可以变换为 $B_2…$。

例如:$A$=abcd $B$=xyz

变换规则为:

abc $\to$ xu ud $\to$ y y $\to$ yz

则此时,$A$ 可以经过一系列的变换变为 $B$,其变换的过程为:

abcd $\to$ xud $\to$ xy $\to$ xyz

共进行了三次变换,使得 $A$ 变换为 $B$。

输入格式

输入格式如下:

$A$ $B$
$A_1$ $B_1$
$A_2$ $B_2$
… …

第一行是两个给定的字符串 $A$ 和 $B$。

接下来若干行,每行描述一组字串变换的规则。

所有字符串长度的上限为 $20$。

输出格式

若在 $10$ 步(包含 $10$ 步)以内能将 $A$ 变换为 $B$ ,则输出最少的变换步数;否则输出 NO ANSWER!

输入样例:

abcd xyz
abc xu
ud y
y yz

输出样例:

3