← 返回题目列表

Codeforces · 2146/B

B. 合并集合

中文机器翻译题面 查看原题

给定您 $$$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".

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

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

注意

在第一个测试用例中,有 $$$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$$$。