페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10456

철도 유지보수 40s 2048MB

문제

철도망의 유지보수를 맡고 있다. 이 철도망은 \mathbf{N}개의 역과 \mathbf{L}개의 노선으로 이루어진다. 각 노선은 일정한 역 목록을 양방향으로 운행한다. (열차는 목록의 첫 역과 마지막 역에서 방향을 바꾼다.) 한 역에서 다른 노선으로 환승할 수 있다. 따라서 역 a에서 역 b로의 이동(여행)이 가능하다는 것은, 어떤 노선들의 목록이 존재하여 그 목록의 첫 노선이 역 a를 포함하고, 마지막 노선이 역 b를 포함하며, 목록에서 이웃한 두 노선마다 공통으로 포함하는 역이 적어도 하나 존재함을 의미한다.

유지보수를 하는 가장 쉬운 방법은 노선 전체를 한 번에, 한 노선씩 순차적으로 운행 중지시키는 것이다. 하지만 어떤 노선은 필수(essential)일 수도 있다. 어떤 노선을 제거하면 어떤 두 역 사이의 이동이 더 이상 불가능해지는 경우가 하나라도 생긴다면, 그 노선은 필수 노선이다.

존재하는 노선들의 목록이 주어질 때, 그중 몇 개가 필수 노선인지 계산하라.


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 정수 두 개 \mathbf{N}, \mathbf{L}이 주어진다. 이는 각각 철도망의 역의 수와 노선의 수이다. 그 다음으로 \mathbf{L}개의 그룹이 이어지며, 각 그룹은 2줄로 이루어진다. 이 중 i번째 그룹의 첫 줄에는 정수 \mathbf{K_i} 하나가 주어지며, 이는 i번째 노선이 지나는 역의 수이다. i번째 그룹의 둘째 줄에는 \mathbf{K_i}개의 정수 \mathbf{S_{i,1}}, \mathbf{S_{i,2}}, \dots, \mathbf{S_{i,{K_i}}}가 주어지며, 이는 i번째 노선이 지나는 역들을 나타낸다.


출력

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


예제 

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
샘플 케이스 #1에서 첫 번째 노선은 역 2로 가는 유일한 노선이므로 필수이다. 다른 노선을 폐쇄해도 어떤 역 쌍 사이의 이동이 불가능해지지 않으므로 그들은 필수가 아니다. 샘플 케이스 #2에서는 필수 노선이 없다. 샘플 케이스 #3은 샘플 케이스 #2와 비슷하지만 마지막 노선이 빠져 있다. 따라서 남은 모든 노선이 필수이다. 샘플 케이스 #4에서는 마지막 노선이 없으면 역 1에서 역 4로 갈 수 없으므로 마지막 노선이 필수이다. 샘플 케이스 #1과 마찬가지로, 이 노선이 이미 모든 역을 연결하므로 다른 노선은 필수가 아니다.

출처

GCJ 2023b D

로그인해야 코드를 작성할 수 있어요.