Optimal Meeting Pairing

Problem Statement

Given the schedules of E employees, each employee provides a list of available time slots. The input for each employee begins with an integer indicating the number of available time slots, followed by that many integers denoting the actual time slots. Two employees can hold a meeting if they share a common available time slot. However, each employee can participate in at most one meeting.

Your task is to compute the maximum number of meetings that can be scheduled.

Formal Description:

Let \(E\) be the number of employees and for each employee \(i\), let \(S_i\) be the set of available time slots. A meeting can occur at time \(t\) if there exist two distinct employees \(i\) and \(j\) such that \(t \in S_i \cap S_j\), provided that neither employee is already scheduled in any other meeting. Determine the maximum number of such meeting pairings.

inputFormat

The input is read from standard input (STDIN). The first line contains a single integer \(E\) representing the number of employees. The following \(E\) lines each describe an employee's availability. Each of these lines starts with an integer denoting the number of available time slots, followed by that many integers which represent the available time slots.

outputFormat

Output a single integer to standard output (STDOUT) representing the maximum number of meetings that can be scheduled.

4
3 1 2 3
3 2 3 4
2 4 5
3 1 5 6

2