레이팅 미적용John Digger는 거대한 일루디움 포스덱스 광산의 소유주이다. 광산은 여러 큰 교차점에서 만나는 갱도들로 이루어져 있다. 일부 광산주와 달리 Digger는 실제로 노동자들의 안녕에 관심이 있어 광산의 구조를 걱정한다. 구체적으로, 어떤 교차점이 붕괴할 경우 광산 한 구역의 노동자들이 다른 노동자들과 단절될 수 있음을 우려한다(알다시피 일루디움 포스덱스는 매우 불안정하다). 이에 대비해 그는 교차점에서 지상으로 통하는 특수 탈출 갱도를 설치하려 한다. 모든 교차점에 탈출 갱도를 하나씩 설치할 수도 있지만, Digger가 노동자들을 그렇게까지 아끼지는 않는다. 대신 어떤 교차점이 붕괴하더라도 그 붕괴에서 살아남은 모든 노동자가 지상으로 가는 경로를 가질 수 있도록 최소 개수의 탈출 갱도를 설치하고 싶어 한다. 탈출 갱도의 최소 개수와, 이 최소 개수의 탈출 갱도를 설치할 수 있는 전체 방법의 수를 계산하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스의 첫 줄에는 광산 갱도의 수를 나타내는 양의 정수 \(N\) (\(N \le 5 \cdot 10^{4}\))이 주어진다. 다음 \(N\)개의 줄에는 각각 서로 다른 두 정수 \(s\)와 \(t\)가 주어지며, \(s\)와 \(t\)는 교차점 번호이다. 교차점 번호는 1부터 연속해서 매겨진다. 각 교차점 쌍은 최대 하나의 갱도로 연결된다. 각 갱도 집합은 하나의 연결된 단위를 이룬다(즉, 어떤 교차점에서든 다른 어떤 교차점으로도 갈 수 있다). 마지막 테스트 케이스 다음에는 0 하나가 있는 줄이 주어진다.
각 테스트 케이스마다 케이스 번호와 함께 갱도 시스템에 필요한 탈출 갱도의 최소 개수와 이 탈출 갱도들을 설치할 수 있는 전체 방법의 수를 출력한다. 결과는 부호 있는 64비트(\(64-bi\)t) 정수 범위에 들어간다고 가정해도 된다. 샘플 출력의 형식을 따른다.
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
ICPC 2011 World Finals Problem H: Mining Your Own Business
Case 1: 2 4
Case 2: 4 1