Background

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

$$A_1​ →B_1​ 。$$

$$A_2​ →B_2​ 。$$

规则的含义为：在$A$中的子串$A_1$可以变换为$B_1$, $A_2$可以变换为$B_2$

例如：$A=abcd,\space B=xyz$

变换规则为：

$$abc​ → xu,\space ud​ →y,\space y ​ → yz$$

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

$$abcd→xud→xy→xyz$$

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

Input

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

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

Output

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

Samples

abcd xyz
abc xu
ud y
y yz

3

Limitation

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