记录编号	344220	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 矿场搭建	最终得分	100
用户昵称	Hzoi_Queuer	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2016-11-10 06:14:28	内存使用	0.27 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=505;
#define LL long long
struct Edge{
	int to,next;
}e[maxn];
int n,m,len,rt,son,ans,cnt,tot,Node,Case=0,Time,head[maxn],dfn[maxn],Low[maxn],vis[maxn];
LL f;
bool flag[maxn],Gd[maxn];
void Insert(int x,int y){
	len++;e[len].to=y;e[len].next=head[x];head[x]=len;
}
void Tarjan(int x){
	Low[x]=dfn[x]=++Time;
	for(int i=head[x];i!=-1;i=e[i].next){
		int j=e[i].to;
		if(!dfn[j]){
			Tarjan(j);
			if(x==rt)son++;
			else{
				Low[x]=min(Low[x],Low[j]);
				if(Low[j]>=dfn[x] && !Gd[x])Gd[x]=1;	
			}
		}
		else Low[x]=min(Low[x],dfn[j]);
	}
}
void Dfs(int x){
	flag[x]=0;
	for(int i=head[x];i!=-1;i=e[i].next){
		int j=e[i].to;
		if(!flag[j])continue;
		if(Gd[j] && vis[j]!=tot)vis[j]=tot,cnt++;
		else if(!Gd[j]){
			Node++;Dfs(j);
		}
	}
}
int main()
{
	freopen("bzoj_2730.in","r",stdin);
	freopen("bzoj_2730.out","w",stdout);
	while(scanf("%d",&m)){
		if(m==0)break;int x,y;
		memset(head,-1,sizeof head);
		memset(flag,0,sizeof flag);
		memset(dfn,0,sizeof dfn);
		memset(Low,0,sizeof Low);
		memset(Gd,0,sizeof Gd);
		n=0,len=0;Time=0;rt=-1;f=1ll;ans=0;Case++;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			if(!flag[x])flag[x]=1,n++;
			if(!flag[y])flag[y]=1,n++;
			Insert(x,y);Insert(y,x);
		}
		for(int i=1;i<=m;i++){
			if(flag[i] && !dfn[i]){
				rt=i;son=0;
				Tarjan(i);
				if(son>1 && !Gd[i])Gd[i]=1;
			}
		}
	//	for(int i=1;i<=m;i++)if(Gd[i])printf("%d ",i);printf("\n");
		for(int i=1;i<=m+1;i++){
			if(!flag[i])continue;
			if(!Gd[i]){
				cnt=0;Node=1;tot++;Dfs(i);
				if(!cnt)ans+=2,f=f*Node*1ll*(Node-1)/2;
				else if(cnt==1)ans++,f=Node*1ll*f;
			}
		}
		printf("Case %d: %d %lld\n",Case,ans,f);
	}
	return 0;
}