该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

$\red{A_1 -> B_1}$

$\red{A_2 -> B_2}$

…

规则的含义为：在 $\red A$ 中的子串 $\red{A_1}$ 可以变换为 $\red{B_1}$、$\red{A_2}$ 可以变换为 $\red{B_2}$ …。

例如：$\red{A＝’abcd’}$ $\red{ B＝’xyz’}$

变换规则为：

$\red{‘abc’->‘xu’}$ $\red{‘ud’->‘y’}$ $\red{‘y’->‘yz’}$

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

$\red{‘abcd’->‘xud’->‘xy’->‘xyz’}$

共进行了三次变换，使得$\red A$ 变换为$\red B$。

输入格式

输入格式如下：

$\red A$ $\red B$

$\red{A_1}$ $\red{ B_1}$

$\red{A_2}$ $\red{B_2}$

|-> 变换规则 … … /

所有字符串长度的上限为$\red{ 20}$。

输出格式

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

样例

输入样例

abcd xyz
abc xu
ud y
y yz

输出样例

3