[NOIP2002 提高组] 字串变换

题目背景

本题疑似错题,不保证存在靠谱的多项式复杂度的做法。测试数据非常的水,各种做法都可以通过,不代表算法正确。因此本题题目和数据仅供参考。

题目描述

已知有两个字串 $A,B$ 及一组字串变换的规则(至多 $6$ 个规则): $A_1\to B_1$ $A_2\to B_2$ 规则的含义为:在 $A$ 中的子串 $A_1$ 可以变换为 $ B_1$,$A_2$ 可以变换为 $B_2\cdots$。 例如:$A=\text{abcd}$,$B=\text{xyz}$, 变换规则为: $\text{abc}\rightarrow\text{xu}$,$\text{ud}\rightarrow\text{y}$,$\text{y}\rightarrow\text{yz}$ 则此时,$A$ 可以经过一系列的变换变为 $B$,其变换的过程为: $\text{abcd}\rightarrow\text{xud}\rightarrow\text{xy}\rightarrow\text{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

说明

**【题目来源】** NOIP 2002 提高组第二题