已知有两个字串 A, B 及一组字串变换的规则（至多6个规则）: A1 -> B1 A2 -> B2 规则的含义为：在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2 …。 例如：A='abcd'　B='xyz' 变换规则为：abc->xu、ud->y、y->yz 则此时，A 可以经过一系列的变换变为 B，其变换的过程为：abcd->xud->xy->xyz 共进行了三次变换，使得 A 变换为B。

输入描述

第一行给出两个字符串 A、B。 接下来若干行每行给出两个字符串 Ai、Bi，表示一条变换规则。 所有字符串长度的上限为 20，变换规则至多6条。

输出描述

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

输入样例1

abcd xyz
abc xu
ud y
y yz

输出样例1

3

提示

NOIP 2002 提高组第二题