Learning Languages

Farmer John's $N$ ($2 \le N \le 10{,}000$) cows, conveniently numbered $1 \ldots N$, are fluent in some $M$ ($1 \le M \le 30{,}000$) languages, also conveniently numbered $1 \ldots M$. Cow $i$ can speak $K_i$ ($1 \le K_i \le M$) languages, namely $L_{i1}, L_{i2}, \ldots, L_{iK_i}$ ($1 \le L_{ij} \le M$). FJ's cows aren't THAT smart, so the sum of $K_i$ over all cows $i$ is at most $100{,}000$.

Two cows can't directly talk to each other unless both speak a common language. However, cows can pass messages along, translating if necessary. In other words, cows $A$ and $B$ can have a conversation if and only if there exists a sequence of cows $T_1, T_2, \ldots, T_k$ such that $A$ and $T_1$ share a language, $T_1$ and $T_2$ share a language, and so on, and $T_k$ and $B$ share a language.

Farmer John wishes that his cows could be even more social, so he wants every cow to be able to socialize with any other cow. He can buy books to teach any one of his cows any language he pleases. Being a fairly frugal farmer, FJ wants to purchase the minimum number of books necessary to enable all of his cows to speak to each other. Help him determine that minimum number of books.

By way of example, suppose there are three cows named Alberta, Bessie, and Contessa along with three languages denoted #1, #2, and #3. Alberta can speak languages #2 and #3, Bessie can speak language #2, and Contessa can speak language #1. Currently, Alberta and Bessie can talk to each other, but Contessa is left alone.

             #1  #2  #3
Alberta           x   x
Bessie            x
Contessa      x

FJ can buy Contessa a book to teach her language #2, after which all three cows share language #2 and can communicate. (Teaching her language #3 would also work, since she could then reach Bessie through Alberta.) Either way, exactly one book is required here.

• Line 1: Two space-separated integers, $N$ and $M$.
• Lines $2 \ldots N+1$: Line $i+1$ describes the languages cow $i$ speaks, as $K_i + 1$ space-separated integers: $K_i, L_{i1}, L_{i2}, \ldots, L_{iK_i}$.

• A single integer: the minimum number of books FJ must purchase so that every cow can communicate (directly or indirectly) with every other cow.