P2581 [ZJOI2005] Genotype

Genotype is a unique gene string.

We can use uppercase English letters $A-Z$ to describe a Genotype, where each letter represents a gene. Define a "split" rule as a triple of uppercase letters $A_1A_2A_3$, meaning $A_1$ can "split" into $A_2A_3$. Given $n$ "split" rules and $k$ Genotypes, determine whether each Genotype can be obtained from a specific string that consists only of the uppercase letter $S$ by applying the "split" rules. If it is possible, output the minimal length of that specific string; otherwise, output `NIE`.

The first line contains an integer $n$, the number of "split" rules. Each of the next $n$ lines contains 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. Each of the next $k$ lines contains a string of uppercase letters representing a Genotype.

$k$ lines: - If no such specific string can produce the Genotype via the "split" rules, output `NIE`. - If there is such a specific string, output the minimal length of that 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