字串变换

题目描述

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

$A_1 \rightarrow B_1$
$A_2 \rightarrow B_2$
...

规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $B_1$、$A_2$ 可以变换为 $B_2$...。

变换规则

• 一次变换只能变换一个子串
• 如果字符串中有多个位置可以应用规则，只能选择其中一个位置进行变换
• 变换是单向的：只能从 $A_i$ 变换为 $B_i$，不能反向变换

输入格式

输入格式如下：

A B
A1 B1
A2 B2
... ...

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

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

注意： 规则的数量不超过 $6$ 个。

输出格式

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

数据范围

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

输入样例

abcd xyz
abc xu
ud y
y yz

输出样例

3

样例解释

初始字符串：$A = \text{"abcd"}$，目标字符串：$B = \text{"xyz"}$

变换规则：

1. $\text{"abc"} \rightarrow \text{"xu"}$
2. $\text{"ud"} \rightarrow \text{"y"}$
3. $\text{"y"} \rightarrow \text{"yz"}$

变换过程：

1. $\text{"abcd"}$ 应用规则1：$\text{"abc"} \rightarrow \text{"xu"}$，得到 $\text{"xud"}$
2. $\text{"xud"}$ 应用规则2：$\text{"ud"} \rightarrow \text{"y"}$，得到 $\text{"xy"}$
3. $\text{"xy"}$ 应用规则3：$\text{"y"} \rightarrow \text{"yz"}$，得到 $\text{"xyz"}$

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

注意事项

1. 不能同时变换多个子串：例如，如果 $A = \text{"aa"}$，$B = \text{"bb"}$，规则为 $\text{"a"} \rightarrow \text{"b"}$，那么需要两步：

   • 第一步：$\text{"aa"} \rightarrow \text{"ba"}$（变换第一个a）
   • 第二步：$\text{"ba"} \rightarrow \text{"bb"}$（变换第二个a）

2. 规则可能产生空字符串：规则中的 $B_i$ 可以是空字符串（表示删除子串 $A_i$）

3. 规则可能使字符串变长或变短

4. 10步限制：如果超过10步才能变换到目标字符串，则输出 NO ANSWER!

时空限制

• 时间限制：1秒
• 空间限制：64MB