Palindromic DNA

Time limit3sMemory limit128 MB

Summary

Decide, given a cyclic DNA alphabet and palindrome constraints on many index subsets with a no-adjacent-change rule, whether a valid ±1/0 edit assignment exists.

Level: Hard8 of 10
Topics: Union-find, Graph, Implementation, Math
Solved: No attempts yet

Problem

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:

Leave it unchanged.
Advance it by one step in the cyclic order (for example, C becomes A).
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.

Input

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.

Output

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.

Examples3

Example 1

Input

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

Expected output

YES
NO

Example 2
Input
```
1 1
A
1: 0
0 0
```
Expected output
```
YES
```
Example 3
Input
```
3 2
AGA
3: 0 1 2
0:
0 0
```
Expected output
```
YES
```