철도 유지보수

당신은 철도 네트워크의 유지보수를 맡고 있다. 네트워크에는 $N$개의 역과 $L$개의 노선이 있다. 각 노선은 정해진 역 목록을 양방향으로 운행한다(열차는 목록의 첫 역과 마지막 역에서 방향을 바꾼다). 역에서는 노선을 갈아탈 수 있다. 역 $a$에서 역 $b$로 가는 이동이 가능하다는 것은, 첫 노선이 $a$를 지나고 마지막 노선이 $b$를 지나며, 목록에서 이웃한 두 노선이 항상 공통으로 지나는 역을 적어도 하나 가진 노선 목록이 존재한다는 뜻이다.

노선을 한 번에 하나씩 운휴하는 것이 가장 간단한 보수 방법이다. 어떤 노선을 제거했을 때 적어도 한 쌍의 역 사이 이동이 불가능해지면, 그 노선은 필수 노선이다.

주어진 노선들 중 필수 노선이 몇 개인지 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 역의 수 $N$과 노선의 수 $L$을 담은 줄로 시작한다.

이어서 $L$개의 묶음이 주어지며, 각 묶음은 두 줄을 차지한다. $i$번째 묶음의 첫 줄에는 $i$번째 노선이 지나는 역의 수 $K_i$가 주어진다. 둘째 줄에는 그 노선이 지나는 역 $K_i$개의 번호 $S_{i,1}, S_{i,2}, \dots, S_{i,K_i}$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 필수 노선의 수이다.

• $1 \le T \le 100$.
• 모든 $i$에 대해 $2 \le K_i \le N$.
• 모든 $i, j$에 대해 $1 \le S_{i,j} \le N$.
• $j \ne j'$인 모든 $i, j, j'$에 대해 $S_{i,j} \ne S_{i,j'}$. 각 노선은 같은 역을 두 번 지나지 않는다.
• 어떤 노선도 운휴하지 않았을 때, 모든 역 쌍 사이의 이동이 가능하다.

예제 케이스 #1에서 첫 번째 노선은 2번 역을 지나는 유일한 노선이므로 필수 노선이다. 다른 노선을 운휴해도 적어도 한 쌍의 역 사이 이동이 불가능해지지 않으므로, 그 노선들은 필수가 아니다.

예제 케이스 #2에는 필수 노선이 없다.

예제 케이스 #3은 예제 케이스 #2와 비슷하지만 마지막 노선이 빠져 있다. 그래서 남은 노선이 모두 필수가 된다.

예제 케이스 #4에서는 마지막 노선이 없으면 1번 역에서 4번 역으로 갈 방법이 없으므로, 마지막 노선이 필수다. 예제 케이스 #1과 마찬가지로 이 노선은 이미 모든 역을 연결하고 있어서 다른 노선은 필수가 아니다.