[NOIP2002-提高] 字串变换

题目描述

已知有两个字串$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$’

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

输入输出格式

输入格式：

输入格式如下：

$A$ $B$
$A_1$ $B_1$
$A_2$ $B_2$ |-> 变换规则

… … /

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

输出格式：

输出至屏幕。格式如下：

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

输入输出样例

输入样例#1：

abcd xyz abc xu ud y y yz

输出样例#1：

3