Barn Assignment

Interview

Time limit2sMemory limit128 MB

Summary
Given each cow's list of acceptable stalls, find the maximum number of cows that can be matched to distinct stalls using bipartite matching.
Level

Medium4 of 10

Topics
Graph, Greedy
Solved
No attempts yet

Problem

Farmer John has built a barn and divided it into M stalls. To keep the barn comfortable, each stall can hold at most one cow.

At first, the cows were assigned arbitrarily, but a problem soon appeared. Each cow will enter only the stalls on its own preference list and refuses every other stall.

Given the list of stalls each cow is willing to enter, compute the maximum number of cows that can be assigned to stalls. Stalls are numbered from 1 to M.

Input

The first line contains N, the number of cows, and M, the number of stalls. (1 ≤ N, M ≤ 200)

Each of the next N lines describes one cow's preference list. For cow i, the line starts with S_i (0 ≤ S_i ≤ M), the number of stalls the cow is willing to enter, followed by S_i distinct stall numbers.

Output

Print the maximum number of cows that can be assigned to stalls.

Examples1

  1. Example 1

    Input
    5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
    Expected output
    4