Misha and Apples
Contest: Codeforces Round 866 (Div. 1)
Difficulty rating: 2800
Tags: brute force, data structures, dp, two pointers

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 format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
2
1
5
3

Editorial:
In this problem, we need to choose which types of apples will be sold in stores with $$$k_i = 0$$$. Let's fix some arrangement of apples and consider the last moment in it when the apples disappeared from the backpack. All the apples that we took after this moment will go into the final answer, and if there was also a store with $$$k_i = 0$$$ among these stores, then the answer is equal to $$$m$$$.
Depending on the arrangement of apples, the moments of the last zeroing may change, so let's find all such moments of time after which disappearance may occur, and for all such moments, let's check if we can reach the end without zeroing, and if we can, then what is the maximum number of apples we can collect after that.
Formally, let's calculate $$$\mathrm{canZero}_i$$$ for all $$$0 \leq i \leq n$$$, equal to 1 if there is such an arrangement of apples that after purchases in stores on the segment $$$[1, i]$$$, the backpack will be empty, and 0 otherwise, with $$$\mathrm{canZero}_0 = 1$$$. Also, let's calculate $$$\mathrm{maxRemain}_i$$$ for all $$$0 \leq i \leq n$$$, equal to 0 if after passing on the segment $$$[i + 1, n]$$$ with an initially empty backpack, we are guaranteed to empty the backpack at least once, otherwise equal to $$$m$$$ if there is a store with $$$k_i = 0$$$ on this segment, otherwise equal to the total number of apples on this segment, with $$$\mathrm{maxRemain}_n = 0$$$.
The second array is easily calculated by definition. Let's consider one of the ways to build the first array. We will build it from left to right. If $$$k_i = 0$$$, then we can guarantee that the backpack will be empty after this store, so the value of $$$\mathrm{canZero}_i$$$ for such $$$i$$$ is 1. Otherwise, consider all the apples in this store. After the $$$i$$$-th store, the apples will disappear if one of these apples was already in the backpack before. Let's find the maximum such $$$j < i$$$ that the store $$$j$$$ contains one of the apples in the store $$$i$$$, or $$$k_j = 0$$$. Now let's find the maximum such $$$s < j$$$ that $$$\mathrm{canZero}_s = 1$$$. Then we check that there will be no disappearances on the segment $$$[s + 1, i - 1]$$$. In this case, $$$\mathrm{canZero}_i = 1$$$, otherwise it is equal to 0.
Then the answer will be $$$\max\limits_{\mathrm{canZero}_i = 1} \mathrm{maxRemain}_i$$$.
Time complexity: $$$\mathcal{O}(n)$$$.