Virus Mutation and Antibody Detection

A virus is represented by its gene sequence using integers from \(0\) to \(G-1\). The virus can mutate according to a set of mutation rules. Each mutation rule is of the form \(x \to S\), meaning that, in the gene sequence, the gene with value \(x\) can be replaced by the fragment \(S\). A mutation is performed by repeatedly replacing any non‐binary gene (i.e. any digit not equal to 0 or 1) using the corresponding rule. When the entire gene sequence becomes composed solely of \(0\) and \(1\), the mutation process is complete.

An antibody is represented as a binary string. An antibody can detect a mutated (binary) gene sequence if its pattern appears as a substring in that sequence. For example, antibody 01011 can detect the sequence 0101110 (since 01011 is a substring), but cannot detect 110110.

For each gene \(i\) where \(2 \le i \le G-1\) (each of which starts as a single-digit gene), the final mutated gene is obtained by recursively replacing every gene that is not \(0\) or \(1\) using the mutation rules. Then, given a set of antibody patterns, determine whether the final mutated gene is detected (i.e. at least one antibody pattern appears as a substring). If it is detected, output YES. Otherwise, output the length (i.e. the number of characters) of the mutated gene (which is the shortest undetected gene since there is exactly one mutation outcome for each starting gene).

Note: It is guaranteed that for each gene \(i\) with \(2 \le i \le G-1\) a mutation rule is provided, and the mutation rules are deterministic.

Mathematical Formulation:

Let \(F(x)\) denote the final mutated sequence for a gene represented by \(x\). Then \[ F(x)=\begin{cases} x & \text{if } x \in \{0,1\},\\ F(s_1)F(s_2)\cdots F(s_k) & \text{if there is a rule } x\to s_1s_2\cdots s_k. \end{cases} \]

For each starting gene \(i\) (\(2 \le i \le G-1\)), check if there exists an antibody string \(A\) such that \(A\) is a substring of \(F(i)\). If yes, output YES. Otherwise, output \(|F(i)|\> (the length of \(F(i)\)).

inputFormat

The input begins with a line containing two integers \(G\) and \(N\) where \(G\) (\(\ge 3\)) is the total number of gene symbols (\(0\) to \(G-1\)) and \(N\) is the number of antibody patterns.

Then, \(G-2\) lines follow, each containing a mutation rule in the format:

x S

Here, x is an integer with \(2 \le x \le G-1\) and S is a non-empty string consisting of digits (each digit is between \(0\) and \(G-1\)).

Then, \(N\) lines follow, each containing a non-empty binary string (consisting of characters 0 and 1) representing an antibody.

outputFormat

For each starting gene \(i\) from \(2\) to \(G-1\) (in increasing order), output a single line. If the final mutated gene \(F(i)\) contains at least one antibody pattern as a substring, print YES. Otherwise, print the length of \(F(i)\) (i.e. the minimal length among undetected genes, noting that there is exactly one outcome per starting gene).

sample

4 2
2 10
3 21
101
010

2
YES

</p>