#P6701. [POI1997] Genotype

[POI1997] Genotype

题目背景

Genotype 是一个独特的基因串。

题目描述

我们可以用大写英文字母 AZA-Z 来描述 Genotype,每个字母就代表一个基因。

规定一种「分裂」规则,由三个大写字母 A1A2A3A_1A_2A_3 组成,代表 A1A_1 可以「分裂」为 A2A3A_2A_3

现在给定 nn 个「分裂」规则和 kk 个 Genotype,判断这些 Genotype 是否能从一个特定的 只包含大写字母 SS 串通过「分裂」规则得到,如果可以的话输出特定的串的长度的最小值,如果不可以的话输出 NIE

输入格式

第一行一个整数 nn 代表「分裂」规则数。
接下来 nn 行每行三个大写字母 A1,A2,A3A_1,A_2,A_3 代表一个「分裂」规则。
接下来一行一个整数 kk 代表给定的 Genotype 数。
接下来 kk 行每行若干个大写字母表示一个 Genotype。

输出格式

kk 行:

  • 如果没有特定的串通过「分裂」规则得到这个 Genotype,输出 NIE
  • 如果有特定的串通过「分裂」规则得到这个 Genotype,输出这个特定的串的最小长度。
6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA
3
1
NIE

提示

数据规模与约定

对于 100%100\% 的数据,1n,k20001 \le n,k \le 2000,Genotype 的长度最大为 100100