Alice is attending a sport event with many national teams and one thing is important to her: supporting every country.
There are $$$N$$$ countries represented and she has two ways to support a country: either have the flag drawn on her or have a pin with the name of the country. Alice has a list containing, for each country, the colours needed to make its flag. A total of $$$M$$$ colours that may appear across all flags and, in Alice's list, each colour is conveniently represented as an integer between 1 and $$$M$$$.
Each crayon and pin cost 1, but her budget is tight... Can you help her find the minimum she can spend to support everyone?
The first line contains the two space-separated numbers $$$N$$$ and $$$M$$$. Then follow $$$2N$$$ lines, grouped in pairs; the $$$(2i-1)^{\text{th}}$$$ and $$$2i^{\text{th}}$$$ lines represent the $$$i^{\text{th}}$$$ country. More precisely, the $$$(2i-1)^{\text{th}}$$$ line contains a single integer $$$k_i$$$: the number of colours in the flag of the $$$i^{\text{th}}$$$ country. Then, the $$$2i^{\text{th}}$$$ line contains $$$k_i$$$ space-separated numbers $$$c_{i,1}, c_{i,2}, \dots , c_{i,k_i}$$$; these are the colours in the flag of the $$$i^{\text{th}}$$$ country.
Limits
- $$$1 \leq N \leq 1\,000$$$;
- $$$1 \leq M \leq 100$$$;
- $$$1 \leq k_i \leq M$$$ for all $$$i \leq N$$$;
- $$$1 \leq c_{i,j} \leq M$$$ for all $$$i \leq N$$$ and $$$j \leq k_i$$$;
- for all $$$i \leq N$$$, the $$$M$$$ colour numbers $$$c_{i,j}$$$ are pairwise distinct.
The output should contain a single line, consisting of a single number: the minimum amount Alice can spend on crayons and pins to represent every country.
7 6 3 1 4 5 3 1 4 5 3 1 4 5 3 3 4 5 3 3 4 5 3 3 4 5 3 2 5 6
5
8 12 2 7 9 12 1 2 3 4 5 6 7 8 9 10 11 12 2 7 9 2 7 9 3 3 4 11 2 7 9 2 7 9 2 7 9
4
Sample Explanation 1
The three first countries could be France, the Netherlands, and the Czech Republic, all represented by blue (1), white (4), and red (5). The three next countries could be Italy, Hungary, and Bulgaria, with green (3), white (4) and red (5). The last one could be Germany, with black (2), red (5), and yellow (6). The minimum cost is 5: we buy four (blue, green, white, and red) crayons and one pin (for Germany).
Sample Explanation 2
We can buy two crayons for the colours 7 and 11 and buy two pins for a total cost of 4. All six countries with flag colours 7 (red) and 11 (white) could be Canada, Indonesia, Japan, Malta, Monaco, and Poland. The flag of Belize has 12 colours, including red and white, and the fifth country could be Botswana.
