Problem C
Piano Lessons

Mrs. Mackenzie loves teaching piano. She started last year with just five students in her home studio at Green Gables in the beautiful province of Prince Edward Island (Canada). Pretty soon, kids across the entire province heard about her brilliant piano teaching, and now she is receiving hundreds of calls requesting lessons. She is finding it very difficult to fit them all into her schedule since she has a limited number of time slots and students have varying availability. While she is baffled by some kids’ irrational interest in sports, she respects their prior commitments.

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
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

Please log in to submit a solution to this problem

Log in