Maximum Cow-Barn Assignment

Farmer John has just built his new milking barn using the latest milking technology. Unfortunately, due to construction issues, each barn stall is different. In the first week, he allowed the cows to choose any stall at will, but soon encountered a problem: each cow only wishes to be milked in certain preferred barns.

Last week, Farmer John collected the preference information for each cow. Each cow lists the barns where she is willing to be milked. Note that each barn can accommodate only one cow, and each cow can only be assigned to one barn.

Your task is to compute the maximum assignment that satisfies all cows' preferences. Mathematically, you are to compute the maximum matching in a bipartite graph:

$$M = \max \{\text{number of pairs } (i, j) \mid i \in \text{Cows},\ j \in \text{Barns}, \text{cow } i \text{ likes barn } j\}\.

inputFormat

The input begins with two integers n and m denoting the number of cows and barns respectively.

Then follow n lines. The i-th line starts with an integer k (the number of barns that the i-th cow likes), followed by k distinct integers representing the barn indices (1-indexed) that the cow prefers.

Note: 1 ≤ n, m ≤ 10⁵ (depending on the problem constraints) and barn indices are between 1 and m.

outputFormat

Output a single integer representing the maximum number of cows that can be assigned to a barn according to their preferences.

sample

3 3
2 1 2
1 1
2 1 3

3