P6701 [POI 1997 R2] Genotype

Genotype is a unique gene string.

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`.

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 $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.

#### 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