Party Invitations

Farmer John is throwing a party and wants to invite some of his cows to show them how much he cares about his herd. Remembering all too well the disaster that resulted the last time he invited too many cows, he also wants to invite as few cows as possible.

Among FJ's cows there are certain groups of friends that are hard to separate. For any such group of size $k$, if FJ invites at least $k-1$ of the cows in the group, then he must invite the final cow as well, thereby including the entire group. Groups can be of any size and may overlap, although no two groups contain exactly the same set of members. The sum of all group sizes is at most $250{,}000$.

The cows are numbered $1$ through $N$ (with $N$ at most $1{,}000{,}000$), and FJ has decided that he must start by inviting cow $1$. Given the groups among FJ's cows, determine the minimum number of cows FJ must invite to his party.

• Line 1: Two space-separated integers $N$ (the number of cows) and $G$ (the number of groups).
• Lines $2 \dots 1+G$: Each line describes a group. It begins with an integer $S$, the size of the group, followed by the $S$ cows in the group (each an integer from $1$ to $N$).

• Line 1: The minimum number of cows FJ must invite to his party.

In the sample there are $10$ cows and $4$ groups; the first group contains cows $1$ and $3$.

In addition to cow $1$, FJ must invite cow $3$ (because of the first group), cow $4$ (because of the second group), and cow $2$ (because of the last group), for a total of $4$ cows.