P1894 [USACO4.2] The Perfect Stall

Last week, Farmer John finished building his new barn, using the latest milking technology. Unfortunately, due to construction issues, every stall is different. In the first week, Farmer John let the cows enter the stalls at random, but problems quickly appeared: each cow will only produce milk in the stalls she likes. Last week, Farmer John collected the cows’ preferences (for each cow, which stalls she likes to use). A stall can hold only one cow, and of course, a cow can be assigned to at most one stall. Given the cows’ preferences, compute the maximum assignment.

The first line contains two integers, $n$ and $m$. $n$ is the number of Farmer John’s cows, and $m$ is the number of stalls in the new barn. Lines $2$ through $n+1$ (a total of $n$ lines) each describe one cow and contain several integers. The first number $s_i$ is the number of stalls this cow is willing to use. The next $s_i$ numbers are the indices of those stalls. Stall indices are in the range $[1,m]$. On the same line, no stall is listed twice.

Output a single line with one integer, the maximum number of stalls that can be assigned.

$0 \le n,m \le 200$, $0 \le s_i \le m$. Translated by ChatGPT 5