[NOIP2002]字串变换

Grade 0 Open Time Wednesday, 16 January 2013, 2:45 pm
Discount 0.8 Time Discount Wednesday, 16 January 2013, 2:45 pm
Allow late Yes Close Time Wednesday, 16 January 2013, 2:45 pm
Input file string.in Output file 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