记录编号	437149	评测结果	EEEEEEEEEE
题目名称	[HNOI 2012] 矿场搭建	最终得分	0
用户昵称	BaDBoY	是否通过	未通过
代码语言	C++	运行时间	0.621 s
提交时间	2017-08-13 18:29:51	内存使用	0.34 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <stack>
#include <vector>
using namespace std;
const int M=500+10;
typedef long long ll;
int t,n,num,cnt,maxn,dex,js;
int head[2*M],dfn[M],low[M],bccb[M],fa[M],son[M];
bool flag[M];
vector<int> bcb[M];
struct DATE{int fr,to,last;}date[2*M];
stack<DATE> sta;
ll ans,an;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void init(){
	ans=1,an=0;
	num=cnt=maxn=dex=0;
	memset(flag,0,sizeof(flag));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(head,0,sizeof(head));
	memset(bccb,0,sizeof(date));
	memset(fa,0,sizeof(fa));
	memset(son,0,sizeof(son));
}
inline void add(int x,int y){
	date[++num]=(DATE){x,y,head[x]};
	head[x]=num;
}
void dfs(int x){
	dfn[x]=low[x]=++dex;
	for(int i=head[x];i;i=date[i].last){
		int to=date[i].to;
		if(!dfn[to]){
			sta.push((DATE){x,to});
			son[x]++;fa[to]=x;dfs(to);
			low[x]=min(low[x],low[to]);
			if(low[to]>=dfn[x]){
				flag[x]=1;cnt++;bcb[cnt].clear();
				DATE tmp;
				do{
					tmp=sta.top();sta.pop();
					if(bccb[tmp.fr]!=cnt){
						bcb[cnt].push_back(tmp.fr);
						bccb[tmp.fr]=cnt;
					}
					if(bccb[tmp.to]!=cnt){
						bcb[cnt].push_back(tmp.to);
						bccb[tmp.to]=cnt;
					}
				}while(tmp.fr!=x&&tmp.to!=to);
			}
		}else{
			if(dfn[to]<dfn[x]&&to!=fa[x]){
				sta.push((DATE){x,to});
				low[x]=min(low[x],dfn[to]);
			}
		}
		if(!fa[x]&&son[x]==1)	flag[x]=0;
	}
}
int main(){
	freopen("bzoj_2730.in","r",stdin);
    freopen("bzoj_2730.out","w",stdout);
	while(scanf("%d",&n)==1&&n){
		init();int aa,bb;
		for(int i=1;i<=n;i++){
			aa=read();bb=read();
			maxn=max(maxn,max(aa,bb));
			add(aa,bb);add(bb,aa);
		}
		for(int i=1;i<=maxn;i++)
			if(!dfn[i])
				dfs(i);
		for(int i=1;i<=cnt;i++){
			int ge=0;
			for(int j=0;j<bcb[i].size();j++)
				if(flag[bcb[i][j]])
					ge++;
			if(ge==1){
				an++;ans*=(ll)(bcb[i].size()-ge);
			}
		}
		if(cnt==1){
			int sz=bcb[1].size();
			an=2;ans=(ll)sz*(ll)(sz-1)/2;
		}
		printf("Case %d: %lld %lld\n",++js,an,ans);
	}
	return 0;
}