Description

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.

Input Format

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 Format

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

2
7 2
3 1 2 4
4 2 4 5 7
3 1
2 1 1

Yes
No

Hint

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