← 返回题目列表

Codeforces · 1819/D

D. 米莎和苹果

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

男生米沙厌倦了做体育节目,所以他决定放弃一切,去魔法森林里卖魔法苹果。

他的朋友丹尼娅来到魔法森林看望米莎。当他发现米莎在那里找到了很多朋友,而且都是前体育程序员时,他感到多么惊讶。他们所有人都像米莎一样,都有自己的商店,出售魔法苹果。为了支持他的朋友们,他们的生活发生了巨大的改变,他决定买下他们的全部品种。

购买过程如下:总共有$$$n$$$个摊位,编号从$$$1$$$到$$$n$$$的整数,还有$$$m$$$种的魔法苹果,编号从$$$1$$$到$$$m$$$的整数。每家商店都出售一定数量的苹果。丹尼娅从第一家商店开始,按照数量递增的顺序参观了所有商店。进入商店后,他买了该商店出售的每种魔法苹果,并将它们放入背包中。

然而,如果魔法苹果没问题的话,它们就不再魔法了。重点是,当两个相同类型的苹果最终一起放入背包时,背包中的所有苹果都会神奇地消失。重要的是,失踪发生在丹尼娅将苹果放入背包并离开商店之后。

回到家后,丹尼娅意识到他在森林的某个地方丢失了背包。不幸的是,丹尼娅忘记了一些商店里有哪些苹果品种。只记得一些商店里卖的是什么种类的魔法苹果,他想知道在他买完所有东西后,他的背包里最多能装多少个苹果。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) - 测试用例的数量。测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$)——摊位数量和苹果种类。

以下 $$$n$$$ 行中的每一行均以下述格式描述下一个摊位的分类。

每行以整数 $$$k_i$$$ 开头 ($$$0 \le k_i \le 2 \cdot 10^5$$$)。接下来是 $$$k_i$$$ 不同的整数 $$$a_{ij}$$$ ($$$1 \le a_{ij} \le m$$$) - 第 $$$i$$$ 个摊位中出售的苹果种类。如果 $$$k_i = 0$$$,那么 Danya 不记得那家商店里有什么品种,并且苹果种类的集合可以是任何东西(包括空的)。

保证所有测试用例的 $$$k_i$$$ 总和不超过 $$$2 \cdot 10^5$$$ 并且所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$

输出

对于每个测试用例,输出一个整数 - 最多访问完所有商店后,Dani 的背包中可以容纳的苹果的最大数量。

示例

输入 #1

4
3 4
2 1 2
2 4 1
2 1 2
4 4
2 1 2
2 3 4
0
1 1
2 5
0
0
5 3
0
3 1 2 3
2 3 1
0
1 3

输出 #1

2
1
5
3

注意

在第一个测试用例中,Danya 记住了所有商店,因此该过程将是确定性的。他会在第一家商店拿两个苹果,在第二家商店再拿两个,但当他把它们放进背包后,它们就会消失。所以最后只剩下 $$$2$$$ 个苹果,他会在第三家商店拿走。

在第二个测试用例中,如果第三个商店是空的,那么在访问第四个商店后所有的苹果都会消失。在任何其他情况下,苹果都会在第三家商店之后消失,而在第四家商店中,丹可以拿一个苹果,所以答案是 $$$1$$$。

在第三个测试用例中,第一家商店可能会出售各种苹果,而第二家商店可能什么也不卖。那么所有 $$$5$$$ 苹果将留在最后。