408223: GYM103059 D Doggis

Doggis is a new kind of dating app... that matches people with lovable pets from the local shelter! After a user creates a profile on the app, the backend generates a list of pets that are compatible with the user. Although the app creators are allowing people to sign up, development of the matching algorithm that pairs users with their new best friends has not yet begun! Internal conflicts ranging from the optimal brand of coffee to buy for the kitchen to whether or not labradoodles are the best dog breed have forced Doggis to hire an independent contractor to write the algorithm for them (while the main team resolves the myriad of existing disputes).

Doggis insists that their matching algorithm maps at most one pet to a single user, and that a user is only matched to a pet on their generated compatibility list. You, the independent contractor, have a heart of gold and want to maximize the number of pets assigned to people for adoption; however, you strongly believe that the constraint that matching at most one pet to a single user is a poor one that works against your ideals. To make your case, you decide to find the number of generated matches from the compatibility lists that will never occur when maximizing the number of pets assigned to people under current constraints. You hope that presenting your findings to the CEO of Doggis, Sehr Pöderman, will convince the company to rethink the desired design of their matching algorithm.

The first line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq M \leq 10^5$$$), representing the number of app users and the number of pets, respectively. Note that pets are represented by unique integers from $$$1$$$ to $$$M$$$, inclusive.

Each of the next $$$N$$$ lines detail a list of pets compatible with a particular user. The first integer on each line, $$$p_i$$$, represents the number of pets compatible with a user. Then $$$p_i$$$ distinct integers between $$$1$$$ and $$$M$$$, inclusive, follow, representing the unique pets compatible with the user. The sum of all $$$p_i$$$ will be at most $$$2 \cdot 10^5$$$.

Output a single integer representing the number of generated user/pet matches that will never occur when maximizing the number of pets assigned to people under current constraints.

3 3
1 1
2 1 2
2 2 3

2

3 3
1 1
1 1
1 1

0