Given Mrs. Mackenzie’s time slots, and a list of the time slots that work for each potential student, can you help her determine the maximum number of students she can fit into her schedule? Note that Mrs. Mackenzie only teaches private lessons (one student at a time) and no student requires more than one time slot.
The first line of input contains two space-separated integers, $N$ and $M$, where $N$ is the number of potential students and $M$ is the number of time slots that Mrs. Mackenzie has available ($1 \leq N, M \leq 1\, 000$). These time slots are numbered $1, 2, 3, \ldots , M$. This is followed by $N$ lines, one for each potential student. Each of these $N$ lines begins with an integer $T$, the number of time slots that work for the student ($0 \leq T \leq M$), and this is followed (on the same line) by $T$ distinct space-separated integers $t_ i$, representing the specific time slots that work ($1 \leq t_ i \leq M$).
Output the maximum number of students Mrs. Mackenzie can fit into her $M$ time slots.
Sample Input 1 | Sample Output 1 |
---|---|
2 3 1 3 1 3 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
5 5 1 1 3 1 2 3 3 1 3 4 3 2 4 5 3 2 3 5 |
5 |