Job Assignment 2

Time limit4sMemory limit256 MB

Summary

Assign each of M jobs to one of N employees who can do it with at most two jobs per employee to handle as many jobs as possible.

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

Problem

Kangho's company has $N$ employees and $M$ jobs to handle. Employees are numbered 1 to $N$ , and jobs are numbered 1 to $M$ .

Each employee can take at most two of the jobs that employee is able to do, and each job is taken by exactly one person.

Given the list of jobs each employee is able to do, write a program that finds how many of the $M$ jobs can be handled at most.

Input

The first line contains the number of employees $N$ and the number of jobs $M$ . ( $1 \le N, M \le 1000$ )

Each of the next $N$ lines describes one employee. The $i$ -th of these lines contains the number of jobs employee $i$ is able to do, followed by the numbers of those jobs.

Output

Print the maximum number of jobs Kangho's company can handle on the first line.

Examples6

Example 1
Input
```
5 5
2 1 2
2 1 2
2 1 2
2 4 5
0
```
Expected output
```
4
```
Example 2
Input
```
1 1
1 1
```
Expected output
```
1
```
Example 3
Input
```
1 1
0
```
Expected output
```
0
```
Example 4
Input
```
2 5
5 1 2 3 4 5
5 1 2 3 4 5
```
Expected output
```
4
```
Example 5
Input
```
3 2
2 1 2
2 1 2
2 1 2
```
Expected output
```
2
```

Example 6

Input

Expected output