Description

There are $n$ students and $m$ classrooms. For classroom $i$, there are $k_i$ students who can take a class there, with indices $p_{i,j}$. Each student has at least one classroom they can attend, and each student can attend only one classroom.

Determine whether there exists an assignment such that each classroom has at least one student. If it is possible, output YES; otherwise, output NO.

Input Format

The first line contains the number of test cases $T$, where $T \leq 10$.

For each test case, the first line contains two integers $m, n$ (note the input order). Then follow $m$ lines: the first number is $k_i$, followed by $k_i$ numbers $p_{i,j}$, indicating that student $p_{i,j}$ can take a class in classroom $i$.

Output Format

For each test case, output one string YES or NO, indicating whether there exists a valid assignment for the corresponding testdata.

2
3 3
3 1 2 3
2 1 2
1 1
3 3
2 1 3
2 1 3
1 1

YES
NO

Hint

Constraints: $n \leq 2 \times 10^4$, $m \leq 2 \times 10^4$, $T \leq 10$.

Translated by ChatGPT 5