已知有两个字串 A,B 及一组字串变换的规则（至多 6 个规则），形如：

• A_1\to B_1。
• A_2\to B_2。

规则的含义为：在 A 中的子串 A_1 可以变换为 B_1，A_2 可以变换为 B_2\cdots。

例如：A=\texttt{abcd}，B＝\texttt{xyz}，

变换规则为：

• \texttt{abc}\rightarrow\texttt{xu}，\texttt{ud}\rightarrow\texttt{y}，\texttt{y}\rightarrow\texttt{yz}。

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

• \texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}。

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

第一行有两个字符串 A,B。

接下来若干行，每行有两个字符串 A_i,B_i，表示一条变换规则。

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

数据范围

对于 100\% 数据，保证所有字符串长度的上限为 20。

NOIP 2002 提高组第二题

双向宽搜