#H513. 字串变换

字串变换

题目描述

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

A1B1A_1→B_1

A2B2A_2→B_2

规则的含义为:在A中的子串A1A_1可以变换为B1B_1A2A_2可以变换为B2B_2…。

例如:A=abcdB=xyz

变换规则为:

abcxu

udy

yyz

则此时,A可以经过一系列的变换变为B,其变换的过程为:

abcdxudxyxyz

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

输入格式

输入格式如下:

A B
A1B1A_1 B_1
A2B2A_2 B_2
… …

第一行是两个给定的字符串A和B。

接下来若干行,每行描述一组字串变换的规则。

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

输出格式

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

abcd xyz
abc xu
ud y
y yz
3