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

$A\_1$ -> $B\_1$

$A\_2$ -> $B\_2$

…

规则的含义为：在 $A$ 中的子串 $A\_1$ 可以变换为 $B\_1$、$A\_2$ 可以变换为 $B\_2$ …。

例如：$A$＝’abcd’ $B$＝’xyz’

变换规则为：

‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’

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

‘abcd’->‘xud’->‘xy’->‘xyz’

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

输入格式

输入格式如下：

$A$ $B$
$A\_1$ $B\_1$ \ $A\_2$ $B\_2$ |-> 变换规则
… … /

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

输出格式

若在 10 步（包含 10步）以内能将 $A$ 变换为 $B$ ，则输出最少的变换步数；否则输出”NO ANSWER!”

输入样例：

abcd xyz
abc xu
ud y
y yz

输出样例：

3

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解