System Engineer

Time limit1sMemory limit128 MB

Summary

Given jobs each with a set of eligible servers, compute the maximum bipartite matching size assigning jobs to distinct servers.

Level: Medium6 of 10
Topics: Graph, BFS, DFS
Solved: No attempts yet

Problem

Bob is a skilled system engineer. He is always facing challenging problems, and now he must solve a new one. He has to handle a set of servers with differing capabilities that process persistent job requests — jobs that must be processed over a long or indefinite period. Persistent job requests arrive one after another, and each request reveals the subset of servers able to service it. A job is processed on a single server, and a server processes only one job. Bob must schedule the maximum number of jobs on the servers. For example, if there are two jobs $j_1$ , $j_2$ and two servers $s_1$ , $s_2$ , and both $j_1$ and $j_2$ require server $s_1$ , then Bob can schedule only one job.

In the general case there are $n$ jobs numbered from $0$ to $n-1$ , $n$ servers numbered from $n$ to $2n-1$ , and a list of job requests. Find the maximum number of jobs that can be processed.

Input

The input is given on standard input and is at most $1\,\text{MB}$ . It may contain several data sets; each data set describes one set of jobs.

A data set starts with the number $n$ ( $n \le 10000$ ) of jobs, followed by the list of required servers for each job in the format:

jobnumber: (nr_servers) s_1 … s_nr_servers

White space (spaces, newlines, etc.) may occur freely anywhere in the input. The input data are always valid and terminate at end of file (EOF).

Output

For each data set, print the maximum number of jobs that can be processed, one per line.

Examples1

Example 1
Input
```
2
0: (1) 2
1: (1) 2
1
0: (1) 1
```
Expected output
```
1
1
```