字串变换

题目描述

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