광산 탈출 수직갱

광산은 여러 교차점에서 만나는 갱도들의 연결망이다. 교차점과 갱도는 하나의 연결된 망을 이루어, 어떤 교차점에서든 갱도를 따라 다른 모든 교차점으로 갈 수 있다.

소유주는 한 교차점이 무너지면 광산의 어느 한 부분에 있는 인부들이 나머지와 단절될 수 있음을 걱정한다. 이를 막기 위해 교차점에 지상으로 통하는 탈출 수직갱을 설치할 수 있다. 모든 교차점에 설치하는 것은 낭비이므로, 대신 다음을 만족하는 탈출 수직갱의 최소 개수를 설치한다: 어떤 한 교차점이 무너지더라도, 그 붕괴에서 살아남은 모든 인부가 남은 갱도를 따라 수직갱이 있는 교차점까지 갈 수 있어야 한다.

필요한 탈출 수직갱의 최소 개수와, 그 최소 개수의 수직갱을 설치하는 서로 다른 방법의 총 수를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스의 첫째 줄에는 갱도의 수인 양의 정수 $N$ ($N \le 5 \cdot 10^4$)이 주어진다. 이어지는 $N$개의 줄에는 각각 서로 다른 두 정수 $s$와 $t$가 주어지며, 이는 갱도로 연결된 두 교차점의 번호이다. 교차점은 $1$부터 연속하여 번호가 매겨진다. 두 교차점을 잇는 갱도는 많아야 하나이며, 각 광산의 갱도는 하나의 연결된 망을 이룬다(어떤 교차점에서든 다른 모든 교차점으로 갈 수 있다).

마지막 테스트 케이스 다음에는 $0$ 하나만 있는 줄이 온다.

각 테스트 케이스마다 케이스 번호 다음에 필요한 탈출 수직갱의 최소 개수와 그 수직갱을 설치하는 방법의 총 수를 출력한다. 결과는 부호 있는 64비트 정수에 들어간다. 출력 형식은 Case X: S W이며, S는 수직갱의 최소 개수, W는 방법의 수이다.