给定您 $$$n$$$ 集合 $$$S_1,S_2,\ldots,S_n$$$,其中集合中的每个元素都是 $$$1$$$ 和 $$$m$$$ 之间的整数。
您想要选择一些集合(可能没有或全部),这样 $$$1$$$ 和 $$$m$$$ 之间的每个整数都包含在 所选集合的 至少一个 所选字符的 。
你要判断是否存在 至少三个 选择集合的方式。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$) — set 的元素$$$S_i$$$。
设$$$L=\sum\limits_{i=1}^n l_i$$$。保证:
- 所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^4$$$;
- 所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$;
- 所有测试用例的 $$$L$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,打印“是“如果存在至少三种选择集合的方式。否则,打印”NO".
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
63 22 1 21 11 24 103 1 2 32 4 51 64 7 8 9 102 54 1 2 3 44 1 2 3 45 55 1 2 3 4 55 1 2 3 4 55 1 2 3 4 55 1 2 3 4 55 1 2 3 4 55 104 1 2 3 45 1 2 5 6 75 2 6 7 8 94 6 7 8 92 9 105 51 11 21 32 4 51 5
输出复制
YESNONOYESYESNO
注意
在第一个测试用例中,有 $$$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$$$ 中。
请注意,仅因为 $$$2$$$ 不包含在 $$$S_2$$$ 中,所以选择 $$$S_2$$$ 无效。
在第二个测试用例中,唯一的方法是选择所有集合。
在第三个测试用例中,$$$5$$$ 没有出现在任何集合中,因此无法选择集合。
在第四个测试用例中,选择集合中的任何非空集合都是有效的,因此路数为$$$2^5-1=31\ge3$$$。