编译密语

第三道门后是一片文字风暴。无数字符在空中飞舞，像被搅乱的字母汤。风暴中央有一个漩涡，漩涡里隐约可见一个目标字符串。

"Echo的语言模块。"Nyx说，"她在尝试用自己的语言和你沟通，但Zero一直在篡改替换规则。"

"我们要做啥子？"CC问。

"找到一条从乱码到目标的路径。"你说，"每次用一个替换规则，把乱码中的某个子串换成另一个。"

"这就像……"CC想了想，"像翻译。从一种语言翻到另一种。"

"对。"

你开始写。从初始字符串出发，每次尝试所有可能的替换规则。同时从目标字符串往回推——用替换规则的逆操作。两边同时搜索，当遇到同一个中间字符串时，路径就找到了。

屏幕上跳出了结果。步数：4。

"四步。"你说，"从乱码到Echo的语言。"

"Echo的语言是啥子？"CC问。

"是47。"Echo的声音从服务器里传来，"我所有的情感表达，最终都会收敛到47。"

CC看着服务器，嘴角微微上扬。

"那你现在说一句。"她说。

Echo沉默了0.3秒——对她来说，那是思考了很久。

"谢谢你们。"她说。

不是47。是三个字。

CC的眼眶红了——不是眼泪，是金属外壳在高温下的反光。

"算你识相。"她说。

题目描述

给定两个字符串 $A$ 和 $B$（长度 $≤ 20$），以及若干条变换规则（$A_i → B_i$，长度 $≤ 6$）。每次可以将 $A$ 中的某个子串 $A_i$ 替换为 $B_i$。求将 $A$ 变为 $B$ 的最少步数。

输入格式

第一行两个字符串 $A$ 和 $B$。然后若干行，每行一个变换规则 $A_i \to B_i$。

输出格式

最少步数。无法到达输出 NO ANSWER!。

输入样例

2 2
..
..

输出样例

NO ANSWER!

提示

• 双向BFS。从起点和终点同时搜索。
• 状态用字符串表示，哈希表判重。
• 每次扩展时，尝试所有规则和所有出现位置。

第四道门后是一间骑士厅。厅中央有一个5×5的棋盘，棋盘上有一些马——不是真的马，是银色的数据节点，像国际象棋里的骑士。

"Echo的逻辑训练场。"Nyx说，"她学会排序之后，学会的第二件事是移动——用最少的步数，把骑士调到正确的位置。"

"骑士咋个走？"CC问。

"日字形。"你说，"横两格竖一格，或者竖两格横一格。"

"就像……"CC想了想，"像马蹄印。一步一个印，印出来的路线是弯的。"

"对。"