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.
Input
The first line of input contains two space-separated
integers, and
, where is the number of potential
students and is the
number of time slots that Mrs. Mackenzie has available
(). These time slots are numbered . This is
followed by lines, one
for each potential student. Each of these lines begins with an integer
, the number of time
slots that work for the student (), and this is
followed (on the same line) by distinct space-separated integers
, representing the
specific time slots that work ().
Output
Output the maximum number of students Mrs. Mackenzie
can fit into her 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
|
