Railroad Maintenance

You are in charge of the maintenance of a railroad network. The network has $N$ stations and $L$ train lines. Each train line serves a fixed list of stations and runs in both directions (trains turn around at the first and last stations of the list). Passengers can transfer between lines at a shared station. A trip from station $a$ to station $b$ is possible if there is a list of train lines such that the first line serves $a$, the last line serves $b$, and every pair of consecutive lines in the list shares at least one station.

Shutting down entire lines is the easiest way to do maintenance, one line at a time. A train line is essential if removing it makes at least one trip between a pair of stations impossible.

Given the existing train lines, count how many of them are essential.

The first line contains the number of test cases $T$. Each test case starts with a line containing two integers $N$ and $L$, the number of stations and train lines.

Then $L$ groups follow, each taking two lines. The first line of the $i$-th group contains $K_i$, the number of stations served by the $i$-th train line. The second line contains $K_i$ integers $S_{i,1}, S_{i,2}, \dots, S_{i,K_i}$, the stations served by that line.

For each test case, output one line in the format Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of essential train lines.

• $1 \le T \le 100$.
• $2 \le K_i \le N$ for all $i$.
• $1 \le S_{i,j} \le N$ for all $i, j$.
• $S_{i,j} \ne S_{i,j'}$ for all $i, j, j'$ with $j \ne j'$. Each train line serves a station at most once.
• With no train line shut down, a trip between every pair of stations is possible.

In Sample Case #1, the first train line is essential because it is the only line serving station $2$. Shutting down any other line does not make a trip between any pair of stations impossible, so they are not essential.

In Sample Case #2, no line is essential.

Sample Case #3 is like Sample Case #2, but the last train line is missing. That makes every remaining train line essential.

In Sample Case #4, the last train line is essential because there is no way to go from station $1$ to station $4$ without it. As in Sample Case #1, this line already connects every station, so no other line is essential.