철도 유지보수

당신은 철도망의 유지보수를 담당한다. 이 철도망은 $\mathbf{N}$개의 역과 $\mathbf{L}$개의 열차 노선으로 이루어진다. 각 열차 노선은 정해진 역 목록을 양방향으로 운행한다(열차는 목록의 첫 역과 마지막 역에서 방향을 바꾼다). 한 역에서 한 노선으로부터 다른 노선으로 환승할 수 있다. 즉, 첫 번째 노선이 역 $a$을 운행하고, 마지막 노선이 역 $b$을 운행하며, 목록에서 연속한 임의의 두 열차 노선마다 두 노선이 모두 운행하는 역이 적어도 하나 존재하는 열차 노선 목록이 있다면, 철도망에서 역 $a$부터 역 $b$까지 이동할 수 있다.

유지보수를 하는 가장 쉬운 방법은 한 번에 하나씩 노선 전체의 운행을 중단하는 것이다. 그러나 일부 열차 노선은 필수적일 수 있다. 어떤 열차 노선을 제거했을 때 적어도 한 역 쌍 사이의 이동이 불가능해진다면, 그 열차 노선은 필수적이다.

현재 존재하는 열차 노선의 목록이 주어질 때, 그중 필수적인 노선의 수를 계산하라.

제한

시간 제한: 40초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $2 \le \mathbf{K_i} \le \mathbf{N}$. 모든 $i, j$에 대해 $1 \le \mathbf{S_{i,j}} \le \mathbf{N}$. $j \ne j'$인 모든 $i, j, j'$에 대해 $\mathbf{S_{i,j}} \ne \mathbf{S_{i,j'}}$(각 열차 노선은 한 역을 최대 한 번 운행한다). 어떤 열차 노선도 운행을 중단하지 않았을 때, 위 정의에 따라 모든 역 쌍 사이를 이동할 수 있다.

테스트 세트 1 (Visible Verdict)

$2 \le \mathbf{N} \le 100$. $1 \le \mathbf{L} \le 100$. $\mathbf{K_1} + \mathbf{K_2} + \cdots + \mathbf{K_L} \le 200$.

테스트 세트 2 (Visible Verdict)

$2 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{L} \le 10^5$. $\mathbf{K_1} + \mathbf{K_2} + \cdots + \mathbf{K_L} \le 2 \times 10^5$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 철도망의 역 수와 열차 노선 수를 나타내는 두 정수 $\mathbf{N}$와 $\mathbf{L}$이 있는 줄로 시작한다. 그다음에는 각각 2줄로 이루어진 $\mathbf{L}$개의 묶음이 주어진다. $i$번째 묶음의 첫 줄에는 $i$번째 열차 노선이 운행하는 역의 수를 나타내는 정수 하나 $\mathbf{K_i}$가 주어진다. $i$번째 묶음의 둘째 줄에는 $i$번째 열차 노선이 운행하는 역을 나타내는 $\mathbf{K_i}$개의 정수 $\mathbf{S_{i,1}}, \mathbf{S_{i,2}}, \dots, \mathbf{S_{i,{K_i}}}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 필수적인 열차 노선의 수이다.

예제 케이스 #1에서는 첫 번째 열차 노선만이 역 $2$을 운행하므로 이 노선은 필수적이다. 다른 어떤 노선의 운행을 중단해도 적어도 한 역 쌍 사이의 이동이 불가능해지지는 않으므로, 다른 노선들은 필수적이지 않다.

예제 케이스 #2에서는 어떤 노선도 필수적이지 않다.

예제 케이스 #3는 예제 케이스 #2과 비슷하지만, 마지막 열차 노선이 없다. 이로 인해 남은 모든 열차 노선이 필수적이다.

예제 케이스 #4에서는 마지막 열차 노선이 없으면 역 $1$에서 역 $4$으로 갈 방법이 없으므로 이 노선은 필수적이다. 예제 케이스 #1에서와 마찬가지로, 이 열차 노선 하나가 이미 모든 역을 연결하므로 다른 어떤 노선도 필수적이지 않다.