P3876 [TJOI2010] Number Sequence

Consider a sequence of length $n$ over digits 0, 1, 2, 3. If it is a valid sequence, it must satisfy both of the following: 1) No adjacent pair appears as any pattern in {'00', '11', '22', '33', '02', '20', '23', '32', '13', '31'}. 2) The sequence satisfies $m$ constraints. Each constraint is of the form {p1, p2, ... pL}, meaning the values at positions $p_1, p_2, \ldots, p_L$ are pairwise distinct. For example, the constraint {1, 5, 11} means the 1st, 5th, and 11th elements are all different. Given $n$, $m$, and these $m$ constraints, determine whether such a valid sequence exists.

The first line contains a positive integer $T$, the number of test cases. For each test case, the first line contains two integers $n$ and $m$ as described above. Then there are $m$ lines, each describing one constraint: in the $i$-th line, the first integer $L_i$ is the size of the constraint, followed by $L_i$ positive integers giving the positions in the $i$-th constraint.

Output $T$ lines. For each test case, print Yes if a valid sequence exists; otherwise, print No.

Constraints: $T \le 10$, $1 \le n \le 100000$, $0 \le m \le 5000$, $1 \le L_i \le 100$, $1 \le p_i \le n$. Time limit per test point: 1 second. In the first sample, the sequence 0103012 is a valid sequence. Translated by ChatGPT 5