Background

Genotype is a unique gene string.

Problem Description

We can use uppercase English letters A-Z to describe a Genotype, where each letter represents one gene.

We define a “split” rule, consisting of three uppercase letters $A_1A_2A_3$, meaning that $A_1$ can “split” into $A_2A_3$.

Now you are given $n$ “split” rules and $k$ Genotypes. Determine whether each Genotype can be obtained from a specific string consisting only of the uppercase letter S by applying the “split” rules. If it can, output the minimum possible length of that specific string. If it cannot, output NIE.

Input Format

The first line contains an integer $n$, the number of “split” rules.
The next $n$ lines each contain three uppercase letters $A_1,A_2,A_3$, representing one “split” rule.
The next line contains an integer $k$, the number of given Genotypes.
The next $k$ lines each contain several uppercase letters, representing one Genotype.

Output Format

Output $k$ lines:

• If no specific string can produce this Genotype by applying the “split” rules, output NIE.
• Otherwise, output the minimum length of such a specific string.

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

3
1
NIE

Hint

Constraints

For $100\%$ of the testdata, $1 \le n,k \le 2000$, and the maximum length of a Genotype is $100$.

Translated by ChatGPT 5