SP10085 PALINDNA - Palindromic DNA

A DNA sequence is composed of a series of four possible nucleobases, namely Adenine, Guanine, Thymine and Cytosine; we will refer to each of these bases by their initial. For our purposes, nucleobases have an associated cyclic “order”: A is followed by G, which in turn is followed by T, which is followed by C, which is followed by A again. State-of-the-art research in genomics has revealed the startling fact that many diseases are caused by certain subsequences of bases not forming a palindromic sequence! Your mission as a leading researcher at ICPC laboratories is to take a DNA string _S_ and a series of subsets _P_ $ _{1} $ , …, _P_ $ _{t} $ of indices to characters (nucleobases) in _S_, and transform _S_ so that each of the restrictions of the resulting string to _P_ $ _{1} $ , …, _P_ $ _{t} $ are palindromic. (The restriction of _S_ to a subset _P_={_i_ $ _{1} $ , _i_ $ _{2} $ , …, _i_ $ _{k} $ } of indices, where 0 i $ _{1} $ < _i_ $ _{2} $ < … < _i_ $ _{k} $ < |_S_|, is the string _S_ $ _{i1} $ _S_ $ _{i2} $ … _S_ $ _{ik} $ ). It is possible to inspect any base of _S_ at will, but only three transformations can be applied to a base: 1. Leave it unaltered. 2. Increase it by 1 in the cyclic order of nucleobases (e.g. turn C into A). 3. Decrease it by 1 (e.g. turn T into G). Moreover, owing to limitations of current technology, it is impossible to modify two bases in consecutive positions of the sequence. Is our goal achievable? By way of example, consider DNA sequence AGTAT. Number positions starting from 0, and suppose we have the three subsets _P_ $ _{1} $ = {1, 4}, _P_ $ _{2} $ = {0, 1} and _P_ $ _{3} $ = {0, 2, 4}. One solution is to increase the first character and decrease the last, yielding _S_′ = GGTAG. The restrictions of _S_′ to _P_ $ _{1} $ , _P_ $ _{2} $ and _P_ $ _{3} $ are GG, GG and GTG, respectively; all of them are palindromic. One case where no solution is possible is when the string is CATGC, and we require the subsequences determined by positions {0,3} and {3,4} be palindromic. Here, characters 3, 0 and 4 would all need to become a T. But this entails modifying consecutive characters 3 and 4, which is not allowed. **Input** The first line of each test case has two integers _N_ and _T_ (1 N T N, all of whose characters are in ACGT. The subsets are described by the following _T_ lines. Each line starts by “_L_:”, where _L_ (0 L N) is the number of positions in the subset, and is followed by _T_ distinct integers between 0 and _N_ − 1 in increasing order. Subsets may overlap partially or totally. A blank line separates different test cases. The input file is terminated by a line containing 0 0. **Output** In a single line per test case, print YES if the task is solvable and NO otherwise. **Sample 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
```
                            

N/A

N/A