P1027

[2002年NOIP提高组]字串变换

时间限制: 5s 内存限制: 64MB 中等 通过 44.32%
描述

已知有两个字串AA, BB及一组字串变换的规则(至多6个规则),形如:
A1B1A_1 \rightarrow B_1
A2B2A_2\rightarrow B_2
规则的含义为:在AA中的子串A1A_1可以变换为B1B_1A2A_2可以变换为B2B_2\cdots
例如:AabcdA='abcd' BxyzB='xyz'
变换规则为:
abcxu udy yyz'abc'\rightarrow 'xu' 'ud'\rightarrow 'y' 'y'\rightarrow 'yz'
则此时,AA可以经过一系列的变换变为BB,其变换的过程为:
abcdxudxyxyz'abcd'\rightarrow 'xud'\rightarrow 'xy'\rightarrow 'xyz'
共进行了三次变换,使得AA变换为BB

输入

第一行为两个字符串,第二行至文件尾为变换规则
AA BB
A1A_1 B1B_1
A2A_2 B2B_2 |-> 变换规则
… … /
所有字符串长度的上限为 20。

输出

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

样例输入
abcd xyz
abc xu
ud y
y yz
样例输出
3