该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

徐老师的集合合并

题目描述

小徐老师给你 $n$ 个集合 $S_{1}, S_{2}, \dots, S_{n}$，其中每个集合里的元素是 $1$ 到 $m$ 之间的整数。

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

请判断是否有至少三种不同的方式选择集合，使上述条件成立。

输入格式

每组测试数据包含多组测试用例。第一行为测试用例组数 $t$（$1 \le t \le 10^4$）。接下来是各组测试数据。

每个测试用例的第一行为两个整数 $n$ 和 $m$（$2 \le n \le 5 \cdot 10^4$，$1 \le m \le 10^5$），分别表示集合数和整数范围上界。

接下来 $n$ 行，第 $i$ 行首先包含一个整数 $l_{i}$（$1 \le l_{i} \le m$），表示第 $i$ 个集合的大小。紧接着包含 $l_{i}$ 个整数 $S_{i,1}, S_{i,2}, \dots, S_{i,l_{i}}$（$1 \le S_{i,1} < S_{i,2} < \dots < S_{i,l_{i}} \le m$），表示 $S_{i}$ 的元素。

记 $L = \sum_{i=1}^{n} l_{i}$。保证：

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

输出格式

对于每个测试用例，如果存在至少三种不同的选择集合的方案，输出 YES，否则输出 NO。

输入输出样例 #1

输入 #1

6
3 2
2 1 2
1 1
1 2
4 10
3 1 2 3
2 4 5
1 6
4 7 8 9 10
2 5
4 1 2 3 4
4 1 2 3 4
5 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 10
4 1 2 3 4
5 1 2 5 6 7
5 2 6 7 8 9
4 6 7 8 9
2 9 10
5 5
1 1
1 2
1 3
2 4 5
1 5

输出 #1

YES
NO
NO
YES
YES
NO

说明/提示

在第一个测试用例中，存在 $5 \ge 3$ 种选择方案：

1. 只选 $S_{1}$，那么 1 和 2 都包含在 $S_{1}$ 中；
2. 选 $S_{1}$ 和 $S_{2}$，那么 1 包含在 $S_{1}$ 和 $S_{2}$，2 包含在 $S_{1}$；
3. 选 $S_{1}$ 和 $S_{3}$，那么 1 包含在 $S_{1}$，2 包含在 $S_{1}$ 和 $S_{3}$；
4. 选 $S_{2}$ 和 $S_{3}$，那么 1 包含在 $S_{2}$，2 包含在 $S_{3}$；
5. 选 $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 \ge 3$。

数据范围与子任务