CF1387C.Viruses

The Committee for Research on Binary Viruses discovered a method of replication for a large family of viruses whose genetic codes are sequences of zeros and ones. Each virus originates from a single gene; for simplicity genes are denoted by integers from $0$ to $G - 1$. At each moment in time a virus is a sequence of genes. When mutation occurs, one of the genes from the sequence is replaced by a certain sequence of genes, according to the mutation table. The virus stops mutating when it consists only of genes $0$ and $1$.

For instance, for the following mutation table: $$ 2 \to \langle 0\ 1 \rangle \\ 3 \to \langle 2\ 0\ 0\rangle\\ 3 \to \langle 1\ 3\rangle\\ 4 \to \langle 0\ 3\ 1\ 2\rangle\\ 5 \to \langle 2\ 1\rangle\\ 5 \to \langle 5\rangle $$ a virus that initially consisted of a single gene $4$, could have mutated as follows: $$ \langle 4 \rangle \to \langle \underline{0\ 3\ 1\ 2} \rangle \to \langle 0\ \underline{2\ 0\ 0}\ 1\ 2 \rangle \to \langle 0\ \underline{0\ 1}\ 0\ 0\ 1\ 2 \rangle \to \langle 0\ 0\ 1\ 0\ 0\ 1\ \underline{0\ 1} \rangle $$ or in another way: $$ \langle 4 \rangle \to \langle \underline{0\ 3\ 1\ 2} \rangle \to \langle 0\ \underline{1\ 3}\ 1\ 2 \rangle \to \langle 0\ 1\ 3\ 1\ \underline{0\ 1} \rangle \to \langle 0\ 1\ \underline{2\ 0\ 0}\ 1\ 0\ 1 \rangle \to \langle 0\ 1\ \underline{0\ 1}\ 0\ 0\ 1\ 0\ 1 \rangle $$

Viruses are detected by antibodies that identify the presence of specific continuous fragments of zeros and ones in the viruses' codes. For example, an antibody reacting to a fragment $\langle 0\ 0\ 1\ 0\ 0 \rangle$ will detect a virus $\langle 0\ 0\ 1\ 0\ 0\ 1\ 0\ 1 \rangle$, but it will not detect a virus $\langle 0\ 1\ 0\ 1\ 0\ 0\ 1\ 0\ 1 \rangle$.

For each gene from $2$ to $G-1$, the scientists are wondering whether a given set of antibodies is enough to detect all viruses that can emerge through mutations from this gene. If not, they want to know the length of the shortest virus that cannot be detected.

It may happen that sometimes scientists don't have any antibodies. Then of course no virus can be detected, so the scientists are only interested in the length of the shortest possible virus that can emerge from the gene mutations.

二进制病毒研究委员会发现了一类遗传编码为 0 和 1 序列的病毒的大量复制方法。每种病毒起源于一个单一基因；为简化起见，基因用 $0$ 到 $G - 1$ 的整数表示。在任意时刻，一种病毒是一串基因序列。当发生变异时，序列中的某个基因会依据变异表被替换为某一特定的基因序列。当病毒仅由基因 $0$ 和 $1$ 构成时，变异过程终止。

例如，对于如下变异表：

$$2 \to \langle 0\ 1 \rangle \\ 3 \to \langle 2\ 0\ 0\rangle\\ 3 \to \langle 1\ 3\rangle\\ 4 \to \langle 0\ 3\ 1\ 2\rangle\\ 5 \to \langle 2\ 1\rangle\\ 5 \to \langle 5\rangle$$

一个初始仅含单个基因 $4$ 的病毒，可能按如下方式变异：

$$\langle 4 \rangle \to \langle \underline{0\ 3\ 1\ 2} \rangle \to \langle 0\ \underline{2\ 0\ 0}\ 1\ 2 \rangle \to \langle 0\ \underline{0\ 1}\ 0\ 0\ 1\ 2 \rangle \to \langle 0\ 0\ 1\ 0\ 0\ 1\ \underline{0\ 1} \rangle$$

或另一种方式：

$$\langle 4 \rangle \to \langle \underline{0\ 3\ 1\ 2} \rangle \to \langle 0\ \underline{1\ 3}\ 1\ 2 \rangle \to \langle 0\ 1\ 3\ 1\ \underline{0\ 1} \rangle \to \langle 0\ 1\ \underline{2\ 0\ 0}\ 1\ 0\ 1 \rangle \to \langle 0\ 1\ \underline{0\ 1}\ 0\ 0\ 1\ 0\ 1 \rangle$$

病毒通过抗体检测，这些抗体识别病毒编码中特定的连续 0 和 1 片段。例如，对片段 $\langle 0\ 0\ 1\ 0\ 0 \rangle$ 产生反应的抗体能检测病毒 $\langle 0\ 0\ 1\ 0\ 0\ 1\ 0\ 1 \rangle$，但无法检测病毒 $\langle 0\ 1\ 0\ 1\ 0\ 0\ 1\ 0\ 1 \rangle$。

对于每个从 $2$ 到 $G-1$ 的基因，科学家们希望知道：给定的一组抗体是否足以检测所有可通过该基因经变异产生的病毒。若不能，则他们希望知道最短的、无法被检测到的病毒的长度。

有时，科学家可能没有任何抗体。此时显然无法检测任何病毒，因此他们只关心：由该基因经变异所能产生的最短病毒的长度。

The first line of the input will contain three integers $G$, $N$ and $M$ ($G \gt 2$, $N \geq G - 2$, $M \geq 0$) specifying the number of genes, the number of rows in the mutation table, and the number of antibodies.

The following $N$ lines contain descriptions of rows of the mutation table; each line begins with two integers $a$ and $k$ ($2 \leq a \lt G$, $k \geq 1$), followed by a sequence of $k$ integers $b_1, b_2, \ldots, b_k$ ($0 \leq b_i \lt G$), that encode the row $$ a \to \langle b_1\ b_2\ \ldots\ b_k \rangle $$

The sum of all values $k$ does not exceed $100$. Every integer from $2$ to $G - 1$ appears in the table as $a$ at least once.

The next $M$ lines contain descriptions of the antibodies; each such line begins with an integer $\ell$ ($\ell \geq 1$), followed by a sequence of $\ell$ integers $c_1, c_2, \ldots, c_\ell$ ($0 \leq c_i \leq 1$), describing the antibody. The sum of all values $\ell$ does not exceed $50$.

输入的第一行包含三个整数 $G$、$N$ 和 $M$（满足 $G \gt 2$，$N \geq G - 2$，$M \geq 0$），分别表示基因总数、突变表的行数以及抗体数量。

接下来的 $N$ 行描述突变表的各行；每行以两个整数 $a$ 和 $k$（满足 $2 \leq a \lt G$，$k \geq 1$）开头，随后是一串 $k$ 个整数 $b_1, b_2, \ldots, b_k$（满足 $0 \leq b_i \lt G$），用于编码该行：

$$a \\to \\langle b\_1\\ b\_2\\ \\ldots\\ b\_k \\rangle$$

所有 $k$ 值之和不超过 $100$。每个从 $2$ 到 $G - 1$ 的整数至少作为某个 $a$ 在表中出现一次。

接下来的 $M$ 行描述各抗体；每行以一个整数 $\ell$（$\ell \geq 1$）开头，随后是一串 $\ell$ 个整数 $c_1, c_2, \ldots, c_\ell$（满足 $0 \leq c_i \leq 1$），用于描述该抗体。所有 $\ell$ 值之和不超过 $50$。

Your program needs to output exactly $G - 2$ lines, containing the answers for the subsequent genes from $2$ to $G - 1$.

If all viruses that can mutate from this single gene can be detected by the given set of antibodies, you need to print the word "YES". You also need to print this if there are no viruses that could originate from this gene (it can happen when the sequences never stop mutating).

Otherwise you need to print the word "NO", followed by an integer denoting the minimal length of the undetectable virus. You can assume that for all the prepared input data this value will be smaller than $2^{63}$.

你的程序需要恰好输出 $G - 2$ 行，分别对应从第 $2$ 个到第 $G - 1$ 个基因的答案。

如果所有能由该单个基因突变而来的病毒均能被给定的抗体集合检测到，则需输出单词 “YES”。当不存在任何可能源自该基因的病毒时（例如，序列永不停止突变），也需输出 “YES”。

否则，需输出单词 “NO”，后跟一个整数，表示不可检测病毒的最小长度。你可以假设：对于所有准备好的输入数据，该值均小于 $2^{63}$。