CF1387C Viruses

二进制病毒研究委员会发现了一种适用于一大类病毒的复制方式，这些病毒的遗传密码是由 $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$，科学家们想知道，给定的抗体集合是否足以检测所有可能由该基因变异产生的病毒。如果不能，他们还想知道无法被检测到的最短病毒的长度是多少。 有时科学家们可能没有任何抗体。这种情况下，当然无法检测到任何病毒，因此他们只关心由该基因变异产生的最短病毒长度。

输入的第一行包含三个整数 $G$、$N$ 和 $M$（$G > 2$，$N \geq G - 2$，$M \geq 0$），分别表示基因的数量、变异表的行数和抗体的数量。 接下来的 $N$ 行描述变异表的每一行；每行以两个整数 $a$ 和 $k$ 开头（$2 \leq a < G$，$k \geq 1$），后跟 $k$ 个整数 $b_1, b_2, \ldots, b_k$（$0 \leq b_i < 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$。

你的程序需要输出恰好 $G-2$ 行，依次对应基因 $2$ 到 $G-1$ 的答案。 如果所有可能由该基因变异产生的病毒都能被给定的抗体集合检测到，输出 "YES"。如果从该基因出发不存在任何病毒（即变异过程永远不会停止），也输出 "YES"。 否则，输出 "NO"，后跟一个整数，表示无法被检测到的最短病毒长度。可以保证对于所有测试数据，这个值都小于 $2^{63}$。

由 ChatGPT 4.1 翻译