Baking Brakedown

Pixabay, cc0
Osquar works at Ericsson, but is not very good at baking. Unfortunately it has now become Friday and as usual one person in the team is supposed to bring “fika" for everyone and this Friday its Osquar’s turn.

When Osquar bakes he does the following. He takes all of the ingredients that are in the recipe, mixes them in his big bowl, pours out the batter on a tray and places it in the oven (that’s what you do when baking right?). However, he doesn’t bother to wash the bowl inbetween different cakes or pastries, so there is a risk that traces of other ingredients which shouldn’t be there still remain in the bowl, contaminating the pastry. This is a big problem becuase of the food preferences in his team. A collegue can only eat a pastry if it’s completly uncontaminated of other ingredients.

Osquar has received $n$ preferences from his $n$ colleauges, which will contain at least one of the $m$ ingredients. Help Osquar to find the maximum number of edible pastries that he can bake for his colleauges at Ericsson, given that he gets to choose in which order he bakes the pastries and that the bowl is clean from the beginning.


The first row contains two integers $n$ and $m$, the number of preferences and the number of available ingredients. Then follows $n$ rows, one for each preference, that contain an integer $k$ and then $k$ integers $a_1...a_ k$, the ingredients in the pastry that can be baked according to their preference.

$1 \leq n \leq 10^6$
$1 \leq k,m \leq 20$
$1 \leq a_ i \leq m$


Output one integer, the maximum number of pastries Osquar can bake.

Explanation: First bake pastry 3, then pastry 2. Pastry 1 cannot be baked if any of the other pastries have been baked due to the bowl being contaminated with ingredient 3. If pastry 1 has been baked neither of the other pastries can be baked since the bowl is contaminated with ingredient 1.

Sample Input 1 Sample Output 1
3 3
2 1 2
2 2 3
1 3