Minimum Vertex Cover

Time limit2sMemory limit128 MB

Summary

Given a bipartite graph with adjacency lists, compute the size of the minimum vertex cover using König's theorem via bipartite matching.

Level: Medium5 of 10
Topics: Graph, BFS, Greedy
Solved: No attempts yet

Problem

You are given a bipartite graph split into two groups, A and B. Group A has N vertices and group B has M vertices. The vertices of A are numbered from 1 to N, and the vertices of B are numbered from 1 to M. The i-th vertex of A is written as Ai, and the j-th vertex of B is written as Bj. Every edge joins one vertex of A with one vertex of B.

A vertex cover is a set of vertices such that every edge of the graph is incident to at least one vertex in the set. In other words, once every vertex in the set is removed, no edge remains. Removing a vertex also removes every edge incident to it.

A minimum vertex cover is a vertex cover whose size (the number of vertices) is as small as possible. Write a program that computes the size of the minimum vertex cover of the given bipartite graph.

Input

The first line contains two integers N and M. (1 ≤ N, M ≤ 1,000)

Each of the next N lines describes one vertex of A: the i-th of these lines first gives k, the number of vertices adjacent to Ai, followed by the k indices j of the B vertices adjacent to Ai. (If Ai has no neighbors, the line contains only 0.)

Output

On the first line, print the size of the minimum vertex cover.

Examples3

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