记录编号	494415	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 矿场搭建	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.074 s
提交时间	2018-04-11 08:43:42	内存使用	0.20 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define LL long long

using namespace std;
void rd(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch<='9' && ch>='0')
		x=x*10+ch-'0',ch=getchar();
	x*=f;
}

const int inf=505;

int m,n;
int tot,fi[inf],nxt[inf<<1],to[inf<<1];
void link(int x,int y){to[++tot]=y;nxt[tot]=fi[x];fi[x]=tot;}

int iscut[inf],bcc_cnt,bccon[inf],bcc_time,dfn[inf],low[inf];
struct ghb{
	int u,v;
}sta[inf];
int top;
vector<int>bcc[inf];

void dfs(int x,int f){
	dfn[x]=low[x]=++bcc_time;
	int child=0;
	for(int i=fi[x];i;i=nxt[i]){
		if(!dfn[to[i]]){//dfn需要初始化
			child++;
			sta[++top]=(ghb){x,to[i]};
			dfs(to[i],x);
			low[x]=min(low[x],low[to[i]]);
			if(low[to[i]]>=dfn[x]){
				iscut[x]=1;
				bcc_cnt++;
				bcc[bcc_cnt].clear();
				while(520){
					ghb a=sta[top--];
					if(bccon[a.u]!=bcc_cnt)bccon[a.u]=bcc_cnt,bcc[bcc_cnt].push_back(a.u);
					if(bccon[a.v]!=bcc_cnt)bccon[a.v]=bcc_cnt,bcc[bcc_cnt].push_back(a.v);
					if(a.u==x && a.v==to[i])break;
				}
			}
		}
		else if(dfn[to[i]]<dfn[x] && to[i]!=f){
			sta[++top]=(ghb){x,to[i]};
			low[x]=min(low[x],dfn[to[i]]);
		}
	}
	if(x==1)iscut[x]=child>1;
}

LL ans;
int num;
int T;

int main(){
	freopen("bzoj_2730.in","r",stdin);
	freopen("bzoj_2730.out","w",stdout);
	while(1){
		rd(m);
		T++;
		if(!m)break;
		n=0;tot=0;top=0;ans=1;num=0;
		memset(bccon,0,sizeof(bccon));
		memset(iscut,0,sizeof(iscut));
		memset(fi,0,sizeof(fi));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		for(int i=1;i<=m;i++){
			int x,y;
			rd(x);rd(y);
			n=max(n,x);n=max(n,y);
			link(x,y);link(y,x);
		}
		bcc_cnt=bcc_time=0;
		dfs(1,0);
		if(bcc_cnt==1)printf("Case %d: %d %d\n",T,2,n*(n-1)/2);
		else {
			for(int i=1;i<=bcc_cnt;i++){
				int cnt=0;
				for(int j=0;j<bcc[i].size();j++)
					if(iscut[bcc[i][j]])cnt++;
				if(cnt==1)ans*=bcc[i].size()-1,num++;
			}
			printf("Case %d: %d %lld\n",T,num,ans);
		}
	}
	return 0;
}