题目描述

给定两个由小写字母组成的字符串 $A$ 和 $B$，以及一组变换规则（至多 $6$ 条）。每条规则形如 $A_i \to B_i$，表示可以将字符串中的子串 $A_i$ 替换为 $B_i$。

例如，若 $A = \texttt{abcd}$，$B = \texttt{xyz}$，规则为：

• $\texttt{abc} \to \texttt{xu}$
• $\texttt{ud} \to \texttt{y}$
• $\texttt{y} \to \texttt{yz}$

则可以通过以下步骤将 $A$ 变换为 $B$：

• $\texttt{abcd} \to \texttt{xud} \to \texttt{xy} \to \texttt{xyz}$

共进行了 $3$ 次变换。

请编写程序，求出将 $A$ 变换为 $B$ 所需的最少步数。

输入格式

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

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

输出格式

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

样例

abcd xyz
abc xu
ud y
y yz

3

提示

所有字符串长度不超过 $20$，且均由小写字母组成。