Palindromic DNA

A DNA sequence is a string over four nucleobases — Adenine, Guanine, Thymine, and Cytosine — which we write using their initials A, G, T, and C. The bases have a cyclic order: A is followed by G, G by T, T by C, and C back to A.

Recent genomics research suggests that some diseases are linked to certain groups of bases failing to read as a palindrome. You are given a DNA string $S$ (indexed from $0$) together with $t$ subsets of positions $P_1, \dots, P_t$, and you must transform $S$ so that, for every subset, the characters of $S$ at those positions read the same forwards and backwards. Formally, the restriction of $S$ to a subset $P = {i_1, i_2, \dots, i_k}$ with $0 \le i_1 < i_2 < \dots < i_k < |S|$ is the string $S_{i_1} S_{i_2} \cdots S_{i_k}$, and every such restriction must be a palindrome.

You may inspect any base, but each base can be changed in only one of three ways:

1. Leave it unchanged.
2. Advance it by one step in the cyclic order (for example, C becomes A).
3. Move it back by one step (for example, T becomes G).

Because of a technological limitation, you may not change two bases that sit in consecutive positions of the sequence. Decide whether the goal is achievable.

For example, take the sequence AGTAT with subsets $P_1 = {1, 4}$, $P_2 = {0, 1}$, and $P_3 = {0, 2, 4}$. Advancing the first base and moving the last base back gives GGTAG; the three restrictions become GG, GG, and GTG, all palindromes, and the two changed positions ($0$ and $4$) are not consecutive.

By contrast, the sequence CATGC with the two subsets ${0, 3}$ and ${3, 4}$ has no solution: positions $0$, $3$, and $4$ would all have to change to the same base (for example T), which forces the consecutive positions $3$ and $4$ to be modified together — and that is forbidden.

The input contains several test cases. The first line of a test case has two integers $N$ and $T$ ($1 \le N \le 10000$, $1 \le T \le 6000$): the length of the sequence and the number of subsets. The next line contains the DNA sequence, a string of length $N$ over the alphabet ACGT.

Each of the following $T$ lines describes one subset. A line begins with L:, where $L$ ($0 \le L \le N$) is the number of positions in the subset, followed by the $L$ distinct positions in strictly increasing order, each between $0$ and $N - 1$. Subsets may overlap partially or completely.

A blank line separates consecutive test cases. The input ends with a line containing 0 0, which must not be processed.

For each test case, print a single line containing YES if all the required restrictions can be made palindromic under the rules, or NO otherwise.