문제
지하 벙커는 M개의 지역과 N개의 터널로 이루어져 있다. 각 터널은 두 지역을 연결하며 양방향으로 통행가능하다.
전쟁 상황에서는 특정 지역이 붕괴하여 통행이 불가능할 수 있다. 이에 대비하기 위해 우리는 몇 개의 지역에 대피소를 만들려고 한다. 대피소를 세웠다면 어떤 지역이 붕괴되더라도 나머지 임의의 지역에서 대피소가 있는 지역으로 이동할 수 있어야 한다.
대피소가 너무 많으면 적군이 침투하기 쉬워지므로, 우리는 최소한의 대피소만 설치하려고 한다. 설치해야 할 대피소의 최소 개수와 최소 개수로 대피소를 설치하는 방법의 수를 구하는 프로그램을 작성하여라.
입력
입력은 여러 개의 테스트케이스로 주어진다.
테스트 케이스의 첫째 줄에 터널의 수 N이 주어진다. (1 ≤ N ≤ 50,000)
테스트 케이스의 둘째 줄부터 N개의 줄에는 각 터널이 연결하는 두 지역 s, t (s ≠ t)가 주어진다. 지역의 번호는 1 이상 M 이하이며(M은 입력으로 주어지지 않는다) 임의의 두 지역을 연결하는 터널은 최대 하나이다. M개의 지역은 터널을 통해 모두 연결되어 있다.
입력의 마지막 줄에는 N=0인 입력이 주어진다.
입력 파일의 크기는 8MB를 넘지 않는다.
출력
각 테스트 케이스별로 필요한 대피소의 최소 개수 A와 대피소를 설치하는 방법의 수 B를 “Case N: A B” 꼴로 출력한다. 정답은 부호가 있는 64비트 정수 자료형으로 표현 가능하다.
예제
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
Case 1: 2 4
Case 2: 4 1
출처
ACM ICPC World Finals 2011
로그인해야 코드를 작성할 수 있어요.