224. [POI 1997] 基因串

【题目描述】

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

我们用大写字母 $S$ 来表示一类被称作超级基因的基因。因为每一个基因串都是由超级基因串(仅包含 $S$)根据给出的规则所分裂出来的。

请写一个程序：

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

【输入格式】

第 $1$ 行包含一个正整数 $m$；

接下来 $m$ 行，每行都包括一个分裂的规则，每个规则由三个大写英文字母组成。

第 $m+2$ 行包含一个正整数 $t$；

接下来 $t$ 行，每行都有一个基因串。

【输出格式】

共 $t$ 行,第 $i$ 行中你应该输出以下内容：

一个正整数，表示可分裂成输入的第 $i$ 个基因串所需的最短超级基因串的长度；

或一个单词 $NIE$（波兰语的“否”），表示无法由超级基因串分裂成该基因串。

【输入样例1】

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

【输出样例1】

3
1
NIE

【输入输出样例2】

点击下载样例2 

【数据规模与约定】

对于其中 $5$ 组数据，$1 \leq m \leq 30，1 \leq t \leq 5$，基因串的长度不超过 $15$。

对于另外 $6$ 组数据，$1 \leq m \leq 20，1 \leq t \leq 5$，基因串的长度不超过 $100$。

对于另外 $4$ 组数据，$1 \leq m \leq 2000，1 \leq t \leq 3000$，基因串的长度不超过 $15$。