Genotype Splitting and Initial String Length

We are given a set of splitting rules and a list of genotype strings. A genotype is described by a string of uppercase English letters (A–Z). Each rule is represented by three letters \(A_1A_2A_3\), meaning that letter \(A_1\) can split into the two‐letter string \(A_2A_3\) (i.e. \(A_1\to A_2A_3\)).

A genotype is obtained by starting from an initial string that consists solely of the letter \(S\) (possibly repeated) and then applying the splitting rules arbitrarily. In any splitting move, any letter for which a rule exists may be replaced by its corresponding two‐letter string. Note that a letter may also be left unsplit. Thus a derived genotype can be seen as the concatenation of portions that are produced starting from one \(S\) (each such portion is derivable from \(S\) by applying a sequence of splits).

Your task is to decide whether each given genotype can be obtained from some initial string of \(S\)'s. If they all can, output the minimum possible length (i.e. the minimum number of \(S\) characters) of such an initial string that can produce all the given genotypes (note that if a genotype can be produced from a single \(S\) then its minimal segmentation is 1, and when multiple genotypes are given, the answer is the maximum over all minimal segmentations). Otherwise, output NIE.

The derivation of a genotype proceeds as follows. A string \(w\) is said to be derivable from a letter \(A\) if either \(w\) equals \(A\) (using no splitting) or there exists a splitting rule \(A\to BC\) and a way to partition \(w\) as \(w = uv\) such that \(u\) is derivable from \(B\) and \(v\) is derivable from \(C\). Finally, a genotype \(g\) is obtainable from an initial string of \(L\) copies of \(S\) if \(g\) can be partitioned into \(L\) (non‐empty) substrings, each of which is derivable from \(S\).

Note: All formulas are written in \(\LaTeX\) format (for example, \(A \to BC\)).

inputFormat

The first line contains two integers \(n\) and \(k\) representing the number of splitting rules and the number of genotype strings respectively.

The next \(n\) lines each contain a rule in the format A1A2A3 (with no spaces) representing the rule \(A_1 \to A_2A_3\).

The following \(k\) lines each contain a genotype string composed solely of uppercase English letters.

outputFormat

If every genotype can be obtained from an initial string composed only of \(S\)'s using the splitting rules, output the minimum possible length of such an initial string (i.e. the minimum number of \(S\) characters required, which is equal to the maximum over the minimal segmentations of the genotypes).

If at least one genotype cannot be obtained, output NIE.

sample

3 3
SAB
ACD
BEE
S
CDEE
SCDEE

2