OI题库

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

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

任务：

请写一个程序：

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

输入格式：

在文本文件GEN.IN的第一行包括一个整数n，1 <= n <= 10000。以下的n行中每行都包括一个成长的规则，每个规则由三个大写英文字母组成。

在该文件的第n+1行包括一个整数k，1 <= k <= 10000。以下的k行中每行都有一个基因串。每个基因串都是一个长度不超过100的大写字符串。

输出格式：

在文件的第i（应共k行）行中你应该输出入下内容：

一个正整数，表示成长为该基因串所需的最短的超级基因串的长度；

或一个单词NIE（波兰语的“否”），如果说无法由超级基因串成长成为该基因串。

样例：

输入

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

输出

3
1
NIE