2638. DNA Sequence

单点时限: 2.0 sec

内存限制: 256 MB

Deoxyribonucleic acid (DNA) is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms and some viruses. The main role of DNA molecules is the long-term storage of information. DNA is often compared to a set of blueprints or a recipe, or a code, since it contains the instructions needed to construct other components of cells, such as proteins and RNA molecules. The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in regulating the use of this genetic information.

DNA structure can be described as DNA sequence, which can only be those consist of following four nucleotides named Adenine, Guanine, Cytosine and Thymine (We can address them A, G, C, T for simplicity). Property varies while the combination of nucleotide changes, thus even a tiny change in the chain of DNA sequence may lead to a completely different appearance.

Prof. Adam C. Murphy is now working on a kind of DNA sequence that has more restrictions than ordinary ones. If a sequence’s substring matches any one of set {‘AA’, ‘CC’, ‘GG’, ‘TT’,‘AC’, ‘CA’, ‘CG’, ‘GC’, ‘GT’, ‘TG’}, the sequence is considered illegal.

Besides, an extra restriction comes: dividing all the position of the sequence in groups as the sets indicate, every nucleotide must be unique in its set. For example, for a given set {{1, 5, 11}, {2, 4}}, the nucleotide in position 1, 5 and 11 must be different for each pair. So it is with position 2 and 4.

Professor Adam C. Murphy wonders, with so many kinds of restrictions, whether a legal DNA sequence exists.


There are several cases in the input.

For each case:

  • The first line: two integers, N (1=<N<=100000) and M (1<=M<=1000). N represents the length of a DNA sequence; M represents the number of restrictions of the second kind.

  • Line 2 to line M+1: each line contains one restriction. An integer ki (ki<=100), followed by ki integers a1,a2…aki,(1<=aki<=N) describing a set we mentioned above.

The position of nucleotides is numbered from 1, and all the numbers are separated by a space.


If such a required sequence exists, print ‘Yes’, otherwise print ‘No’.


ATAGATC is a legal DNA sequence for the sample.


7 2
3 1 2 4
4 2 4 5 7

0 人解决,0 人已尝试。

0 份提交通过,共有 0 份提交。

9.9 EMB 奖励。

创建: 11 年前.

修改: 2 年,11 月前.

最后提交: N/A.

来源: 多校联合比赛BNU站