[NOIP2002]字串变换

成绩 0 开启时间 2013年01月16日 星期三 14:45
折扣 0.8 折扣时间 2013年01月16日 星期三 14:45
允许迟交 是 关闭时间 2013年01月16日 星期三 14:45
输入文件 string.in 输出文件 string.out

[问题描述]

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

A1\$ -> B1\$

A2\$ -> B2\$

规则的含义为：在A\$中的子串A1\$可以变换为B1\$、A2\$可以变换为B2\$…。

例如：A\$＝'abcd'  B\$＝'xyz'

变换规则为：‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’

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

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

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

[输入]

A\$ B\$

A1\$ B1\$

A2\$ B2\$  |->变换规则

... ... / 

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

[输出]

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

[输入样例] 

abcd xyz
abc xu
ud y
y yz

[输出样例] 

3