#P6701. [POI1997] Genotype
[POI1997] Genotype
题目背景
Genotype 是一个独特的基因串。
题目描述
我们可以用大写英文字母 来描述 Genotype,每个字母就代表一个基因。
规定一种「分裂」规则,由三个大写字母 组成,代表 可以「分裂」为 。
现在给定 个「分裂」规则和 个 Genotype,判断这些 Genotype 是否能从一个特定的 只包含大写字母 的 串通过「分裂」规则得到,如果可以的话输出特定的串的长度的最小值,如果不可以的话输出 NIE
。
输入格式
第一行一个整数 代表「分裂」规则数。
接下来 行每行三个大写字母 代表一个「分裂」规则。
接下来一行一个整数 代表给定的 Genotype 数。
接下来 行每行若干个大写字母表示一个 Genotype。
输出格式
行:
- 如果没有特定的串通过「分裂」规则得到这个 Genotype,输出
NIE
。 - 如果有特定的串通过「分裂」规则得到这个 Genotype,输出这个特定的串的最小长度。
6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA
3
1
NIE
提示
数据规模与约定
对于 的数据,,Genotype 的长度最大为 。