题目描述

You are in charge of the maintenance of a railroad network. The network consists of $\mathbf{N}$ stations and $\mathbf{L}$ train lines. Each train line serves a fixed list of stations bidirectionally (trains turn around in the first and last stations of the list). Transfers from one line to another in a station are possible, which means a trip in the network from station $a$ to station $b$ is possible if there is a list of train lines such that the first one serves station $a$, the last one serves station $b$, and for any consecutive pair of train lines in the list there is at least one station that they both serve.

The easiest way to do maintenance is to shut down entire lines, one at a time. However, some train lines may be essential. A train line is essential if removing it would make at least one trip between a pair of stations not possible.

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

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case starts with a line containing two integers $\mathbf{N}$ and $\mathbf{L}$: the number of stations and train lines in the network. Then, $\mathbf{L}$ groups of 2 lines follow. The first line of the $i$-th group contains a single integer $\mathbf{K}_i$ the number of stations served by the $i$-th train line. The second line of the $i$-th group contains $\mathbf{K}_i$ integers $\mathbf{S}_{i,1}, \mathbf{S}_{i,2}, \ldots, \mathbf{S}_{i,\mathbf{K}_i}$ representing the stations served by the $i$-th train line.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of train lines that are essential.

4
4 3
3
1 2 3
2
1 4
3
4 1 3
4 4
2
1 2
2
3 4
2
3 2
2
4 1
4 3
2
1 2
2
3 4
2
3 2
4 3
2
1 2
2
3 4
4
4 1 2 3

Case #1: 1
Case #2: 0
Case #3: 3
Case #4: 1

提示

Sample Explanation

In Sample Case #1, the first train line is essential because it is the only one serving station $2$. Since shutting any other line down would not make travel between at least one pair of stations impossible, they are not essential.

In Sample Case #2, no line is essential.

Sample Case #3 is similar to Sample Case #2, but missing the last train line. That makes all remaining train lines essential.

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

Sample Explanation

• $1 \leq \mathbf{T} \leq 100$.
• $2 \leq \mathbf{K}_i \leq \mathbf{N}$ for all $i$.
• $1 \leq \mathbf{S}_{i,j} \leq \mathbf{N}$, for all $i, j$.
• $\mathbf{S}_{i,j} \neq \mathbf{S}_{i,j'}$, for all $i, j, j'$ such that $j \neq j'$ (Each train line serves a station at most once).

The trip between all pairs of stations is possible as per the definition above when no train line is shut down.

Test Set 1 (9 Pts, Visible Verdict)

• $2 \leq \mathbf{N} \leq 100$.
• $1 \leq \mathbf{L} \leq 100$.
• $\mathbf{K}_1 + \mathbf{K}_2 + \cdots + \mathbf{K}_\mathbf{L} \leq 200$.

Test Set 2 (20 Pts, Visible Verdict)

• $2 \leq \mathbf{N} \leq 10^5$.
• $1 \leq \mathbf{L} \leq 10^5$.
• $\mathbf{K}_1 + \mathbf{K}_2 + \cdots + \mathbf{K}_\mathbf{L} \leq 2 \times 10^5$.