Scheduling Conference Conflicts

You are given a schedule of conferences. Each conference is identified by a unique integer ID and occupies one or more time slots. A conflict occurs if two or more conferences use the same time slot. Your task is to determine the minimum number of conferences that must be rescheduled so that no time slot is occupied by more than one conference.

Formally, let \( \mathcal{C} \) be the set of conferences. For each conference \( c \) with ID \( c\_id \), you are given a set of time slots \( T_c \). A conflict happens on time slot \( t \) if \( \left| \{ c \in \mathcal{C} : t \in T_c \} \right| > 1 \). You need to remove (reschedule) a minimum subset \( \mathcal{R} \subseteq \mathcal{C} \) such that for every time slot \( t \), at most one of the remaining conferences uses \( t \).

This problem may be thought of as selecting a maximum set of non-conflicting conferences (or equivalently, a minimum vertex cover in the conflict graph) under a greedy strategy.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
cid1 t1,1 t1,2 ... t1,k1
cid2 t2,1 t2,2 ... t2,k2
...
cidn tn,1 tn,2 ... tn,kn

Here, the first line contains a single integer \( n \) indicating the number of conferences. Each of the following \( n \) lines describes one conference. The first integer on each line is the conference ID (a positive integer) followed by one or more integers which represent the time slots during which the conference is scheduled.

outputFormat

Output a single integer to standard output (stdout), representing the minimum number of conferences that need to be rescheduled so that no time slot is used by more than one conference.

3
1 1 2
2 2 3
3 1 3

1