题目描述

基因串是由一串有限长度的基因所组成的，其中每一个基因都可以用 $26$ 个英文大写字母中的一个来表示，不同的字母表示不同的基因类型。一个单独的基因可以生长成为一对新的基因，而可能成长的规则是通过一个有限的成长规则集所决定的。每一个成长的规则可以用三个大写英文字母 $a_1,a_2,a_3$ 来描述，这个规则的意思是基因 $a_1$ 可以成长为一对基因 $a_2,a_3$。

我们用大写字母 $s$ 来表示一类被称作超级基因的基因。因为每一个基因串都是由一串超级基因根据给出的规则所成长出来的。

请写一个程序：

• 读入有限条成长的规则和一些我们想要得到的基因串；
• 对于每个基因串，试判断它是否可以由一个有限长度的超级基因串成长得出。如果可以，那么请给出可成长为该基因串的最短超级基因串的长度；
• 把结果输出。

输入格式

第一行包括一个整数 $n$。以下的 $n$ 行中每行都包括一个成长的规则，每个规则由三个大写英文字母组成。在该文件的第 $n+1$ 行包括一个整数 $k$。以下的 $k$ 行中每行都有一个基因串。每个基因串都是一个长度不超过 $100$ 的大写字符串。

输出格式

如果说无法由超级基因串成长成为该基因，则输出 NIE，否则输出一个正整数，表示成长为改基因串所需的最短的超级基因串的长度。

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCCBA

3
1
NIE

数据规模与约定

对于 $100\%$ 的数据，$1\le n,k\le 10^4$。