SP10085 PALINDNA - Palindromic DNA

DNA 序列由四种核苷酸组成：腺嘌呤（A）、鸟嘌呤（G）、胸腺嘧啶（T）和胞嘧啶（C）。这些碱基有一个循环的顺序：A 之后是 G，G 之后是 T，T 之后是 C，C 之后又循环回 A。基因组学的研究发现，许多疾病是由于某些不形成回文序列的碱基子序列引起的！作为 ICPC 实验室的顶尖研究员，你的任务是对一个 DNA 字符串 $S$ 和一些字符索引的子集 $P_1, \ldots, P_t$ 进行修改，使得每个子集对应的字符串子序列都是回文。（字符串 $S$ 在索引子集 $P=\{i_1, i_2, \ldots, i_k\}$ 上的限制，就是从该位置挑选的 $S_{i1} S_{i2} \ldots S_{ik}$）。你可以随意检查 $S$ 的任意碱基，但只能进行以下三种操作： 1. 保持碱基不变。 2. 在循环顺序中将其向后移动 1 位（例如将 C 改为 A）。 3. 在循环顺序中将其向前移动 1 位（例如将 T 改为 G）。 然而，由于技术限制，不能修改序列中相邻位置的两个碱基。我们的任务能否完成呢？ 例如， DNA 序列 AGTAT，从 0 开始编号位置，假设有三个子集 $P_1 = \{1, 4\}$、$P_2 = \{0, 1\}$ 和 $P_3 = \{0, 2, 4\}$。一种办法是将第一个字符增加 1，并将最后一个字符减少 1，得到 $S' = GGTAG$。$S'$ 在 $P_1$、$P_2$ 和 $P_3$ 上的子序列分别为 GG、GG 和 GTG，全都是回文序列。 反之，一个无解的例子是字符串 CATGC，要求位置 {0, 3} 和 {3, 4} 的子序列是回文序列。在这种情况下，字符位置 3、0 和 4 都需变为 T，但这意味着要调整相邻的字符 3 和 4，这违反了规则。

每组测试数据的第一行包含两个整数 $N$ 和 $T$（$1 \leq N \leq 5000$，$1 \leq T \leq 5000$），表示 DNA 序列的长度和子集的数量。接下来的一行是一个长度为 $N$ 的字符串 $S$，其中的字符均为 ACGT 中的一个。接下来的 $T$ 行提供了各个子集的信息。每行以 "$L$ :" 开头，其中 $L$（$0 \leq L \leq N$）表示子集中位置的数量，紧随其后的是 $L$ 个递增的整数，范围从 0 到 $N-1$。子集可能部分或完全重叠。 测试数据之间使用空行分隔。输入以一行 `0 0` 结束。

对于每组测试数据，单独输出一行，若任务可完成则输出 `YES`，否则输出 `NO`。 ## 样例输入 ``` 5 3 AGTAT 2: 1 4 2: 0 1 3: 0 2 4 5 3 CATGC 0: 2: 0 3 2: 3 4 0 0 ``` **本翻译由 AI 自动生成**