CF2146B.Merging the Sets

You are given $n$ sets $S_1,S_2,\ldots,S_n$, where each element in the sets is an integer between $1$ and $m$.

You want to choose some of the sets (possibly none or all), such that every integer between $1$ and $m$ is included in at least one of the chosen sets.

You have to determine whether there exist at least three ways to choose the sets.

给你 $n$ 个集合 $S_1, S_2, \ldots, S_n$，其中每个集合中的元素均为 $1$ 到 $m$ 之间的整数。

你需要从中选出若干个集合（可以一个都不选，也可以全部选择），使得 $1$ 到 $m$ 之间的每个整数至少出现在所选集合中的一个里。

你需要判断：是否存在至少三种不同的选法。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 5\cdot 10^4$, $1\le m \leq 10^5$) — the number of sets and the upper bound of the integers in the sets.

Then $n$ lines follow, the $i$-th line first containing an integer $l_i$ ($1\le l_i\le m$) — the size of set $S_i$.

Then $l_i$ integers $S_{i,1}, S_{i,2}, \ldots, S_{i, l_i}$ follow in the same line ($1\le S_{i,1} \lt S_{i,2} \lt \cdots \lt S_{i, l_i}\le m$) — the elements of set $S_i$.

Let $L=\sum\limits_{i=1}^n l_i$. It is guaranteed that:

• The sum of $n$ over all test cases does not exceed $5\cdot 10^4$;
• The sum of $m$ over all test cases does not exceed $10^5$;
• The sum of $L$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 5\cdot 10^4$，$1\le m \leq 10^5$）——分别表示集合的数量以及集合中整数的上界。

接下来是 $n$ 行，其中第 $i$ 行首先包含一个整数 $l_i$（$1\le l_i\le m$）——表示集合 $S_i$ 的大小。

随后在同一行给出 $l_i$ 个整数 $S_{i,1}, S_{i,2}, \ldots, S_{i, l_i}$（$1\le S_{i,1} \lt S_{i,2} \lt \cdots \lt S_{i, l_i}\le m$）——即集合 $S_i$ 的元素。

令 $L=\sum\limits_{i=1}^n l_i$。保证以下条件成立：

• 所有测试用例中 $n$ 的总和不超过 $5\cdot 10^4$；
• 所有测试用例中 $m$ 的总和不超过 $10^5$；
• 所有测试用例中 $L$ 的总和不超过 $2\cdot 10^5$。

For each test case, print "YES" if there exist at least three ways to choose the sets. Otherwise, print "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，如果存在至少三种选择这些集合的方式，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答。

In the first test case, there are $5\ge 3$ possible ways to choose the sets:

• $S_1$ — both $1$ and $2$ are included in $S_1$;
• $S_1$ and $S_2$ — $1$ is included in $S_1$ and $S_2$, and $2$ is included in $S_1$;
• $S_1$ and $S_3$ — $1$ is included in $S_1$, and $2$ is included in $S_1$ and $S_3$;
• $S_2$ and $S_3$ — $1$ is included in $S_2$, and $2$ is included in $S_3$;
• $S_1$, $S_2$, and $S_3$ — $1$ is included in $S_1$ and $S_2$, and $2$ is included in $S_1$ and $S_3$.

Note that it is invalid to choose $S_2$ only because $2$ is not included in $S_2$.

In the second test case, the only way is to choose all the sets.

In the third test case, $5$ does not appear in any of the sets, so there is no way to choose the sets.

In the fourth test case, choosing any non-empty collection of the sets is valid, so the number of ways is $2^5-1=31\ge3$.

在第一个测试用例中，共有 $5\ge 3$ 种可能的方式选择集合：

• 仅 $S_1$ — $1$ 和 $2$ 均属于 $S_1$；
• $S_1$ 和 $S_2$ — $1$ 属于 $S_1$ 和 $S_2$，且 $2$ 属于 $S_1$；
• $S_1$ 和 $S_3$ — $1$ 属于 $S_1$，且 $2$ 属于 $S_1$ 和 $S_3$；
• $S_2$ 和 $S_3$ — $1$ 属于 $S_2$，且 $2$ 属于 $S_3$；
• $S_1$、$S_2$ 和 $S_3$ — $1$ 属于 $S_1$ 和 $S_2$，且 $2$ 属于 $S_1$ 和 $S_3$。

注意：仅选择 $S_2$ 是无效的，因为 $2$ 不在 $S_2$ 中。

在第二个测试用例中，唯一可行的方式是选择所有集合。

在第三个测试用例中，$5$ 不出现在任何一个集合中，因此不存在满足条件的集合选择方式。

在第四个测试用例中，任意非空的集合子集均有效，因此方案数为 $2^5-1=31\ge3$。