题目描述

给定 $n$ 个集合 $S_1,S_2,\dots,S_n$（即每个 $S_i$ 内部的所有元素都是严格单调递增的），集合中元素均为整数，取值范围为 $1$ 到 $m$（包含端点）。

你需要从这 $n$ 个集合中选择若干个集合（可以不选，也可以全选），要求所选集合的并集覆盖 $1,2,\dots,m$ 中的每一个整数（即每个整数至少出现于一个被选集合中）。

请判断是否存在 至少三种不同的选择方式（即不同的被选集合的子集）满足上述覆盖要求。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。接下来描述 $t$ 个测试用例。

每个测试用例格式如下：

• 第一行包含两个整数 $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$），表示集合 $S_i$ 的大小；随后跟随 $l_i$ 个 严格递增 的整数 $S_{i,1},S_{i,2},\dots,S_{i,l_i}$（$1\le S_{i,1}<S_{i,2}<\cdots<S_{i,l_i}\le m$），表示集合 $S_i$ 的元素。

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

• 所有测试用例中 $\sum n \le 5\cdot 10^4$；
• 所有测试用例中 $\sum m \le 10^5$；
• 所有测试用例中 $\sum L \le 2\cdot 10^5$。

输出格式

对于每个测试用例，若存在至少三种满足条件的选择方式，输出 YES，否则输出 NO。

样例输入

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

样例输出

YES
NO
NO
YES
YES
NO

说明

样例 1 解释

共有 $5$（$\ge 3$）种不同的满足覆盖 $1..2$ 的选择方式

• $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$ 中。

所以输出 YES。

样例 2 解释

唯一可行的选择是选取全部集合，因此只有 $1$ 种，输出 NO。

样例 3 解释

元素 $5$ 没有出现在任何集合中，因此不存在覆盖所有 $1..5$ 的选择，输出 NO。

样例 4 解释

每个元素 $1..10$ 都被至少一个集合覆盖，并且任意非空子集都能覆盖全部元素，所以共有 $2^5-1=31\ge3$ 种，输出 YES。