310334: CF1819D. Misha and Apples

D. Misha and Applestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Schoolboy Misha got tired of doing sports programming, so he decided to quit everything and go to the magical forest to sell magic apples.

His friend Danya came to the magical forest to visit Misha. What was his surprise when he found out that Misha found a lot of friends there, the same former sports programmers. And all of them, like Misha, have their own shop where they sell magic apples. To support his friends, who have changed their lives so drastically, he decided to buy up their entire assortment.

The buying process works as follows: in total there are $n$ stalls, numbered with integers from $1$ to $n$, and $m$ kinds of magic apples, numbered with integers from $1$ to $m$. Each shop sells some number of kinds of apples. Danya visits all the shops in order of increasing number, starting with the first one. Upon entering the shop he buys one magic apple of each kind sold in that shop and puts them in his backpack.

However, magical apples wouldn't be magical if they were all right. The point is that when two apples of the same type end up together in the backpack, all of the apples in it magically disappear. Importantly, the disappearance happens after Danya has put the apples in the backpack and left the shop.

Upon returning home, Danya realized that somewhere in the forest he had managed to lose his backpack. Unfortunately, for some shops Danya had forgotten what assortment of apples there was. Remembering only for some shops, what kinds of magical apples were sold in them, he wants to know what is the maximum number of apples he could have in his backpack after all his purchases at best.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^5$) —the number of test cases. The description of test cases follows.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 2 \cdot 10^5$) —the number of stalls and kinds of apples.

Each of the following $n$ lines describes the assortment of the next stall in the format described below.

Each line starts with an integer $k_i$ ($0 \le k_i \le 2 \cdot 10^5$). This is followed by $k_i$ of different integers $a_{ij}$ ($1 \le a_{ij} \le m$) —the kinds of apples sold in the $i$-th stall. If $k_i = 0$, then Danya does not remember what assortment was in that shop, and the set of apple kinds can be anything (including empty).

It is guaranteed that the sum of all $k_i$ over all test cases does not exceed $2 \cdot 10^5$ and the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$

Output

For each test case, output a single integer — the maximum number of apples that could be in Dani's backpack after visiting all the shops at best.

ExampleInput

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

Output

2
1
5
3

Note

In the first test case, Danya remembers all the shops, so the process will be deterministic. He will take two apples at the first shop and two more at the second, but after he puts them in his backpack, they will disappear. So at the end there will only be $2$ apples left, which he will take at the third shop.

In the second test case, if the third shop is empty, then after visiting the fourth shop all the apples will disappear. In any other case the apples will disappear after the third shop, and in the fourth shop Dan can take one apple, so the answer is $1$.

In the third test case, the first shop may sell all kinds of apples, and the second shop may sell nothing. Then all $5$ apples will be left at the end.

**题目大意：**

米莎厌倦了做体育编程，所以他决定放弃一切，去神奇的森林卖魔法苹果。他的朋友达尼亚来到神奇的森林拜访米莎。当他发现米莎在那里找到了很多朋友，同样是前体育程序员时，他感到非常惊讶。他们和米莎一样，都有自己的商店卖魔法苹果。为了支持这些彻底改变生活朋友们，他决定买下他们的全部商品。

购买过程如下：总共有 $ 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 $，则达尼亚不记得那个商店有什么样的商品，苹果种类可以是任何（包括空）。

保证所有测试用例的所有 $ k_i $ 之和不超过 $ 2 \cdot 10^5 $，所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。

**输出数据格式：**

对于每个测试用例，输出一个整数 —— 达尼亚在访问所有商店后，他的背包中可能有的苹果的最大数量。**题目大意：** 米莎厌倦了做体育编程，所以他决定放弃一切，去神奇的森林卖魔法苹果。他的朋友达尼亚来到神奇的森林拜访米莎。当他发现米莎在那里找到了很多朋友，同样是前体育程序员时，他感到非常惊讶。他们和米莎一样，都有自己的商店卖魔法苹果。为了支持这些彻底改变生活朋友们，他决定买下他们的全部商品。 购买过程如下：总共有 $ 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 $，则达尼亚不记得那个商店有什么样的商品，苹果种类可以是任何（包括空）。 保证所有测试用例的所有 $ k_i $ 之和不超过 $ 2 \cdot 10^5 $，所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出数据格式：** 对于每个测试用例，输出一个整数 —— 达尼亚在访问所有商店后，他的背包中可能有的苹果的最大数量。