记录编号	343579	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 矿场搭建	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2016-11-09 15:17:23	内存使用	0.25 MiB

#include <iostream>
#include <stdio.h>
#include <cstring>
#define Mem(a,v) memset(a,v,sizeof a)
#include <algorithm>
using namespace std;
/******************************************\
freopen(".in","r",stdin);
	freopen(".out","w",stdout);
\******************************************/
void qkin(int &res){
	int x,f=1; char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	res = x * f;
}
void read(int &a){ qkin(a); }
void read(int &a,int &b){ qkin(a); qkin(b); }
void read(int &a,int &b,int &c){ qkin(a); qkin(b); qkin(c); }
typedef long long LL;
#define maxn 1010
int Case = 0;
int T,m;//最大点   边数 
LL ans1,ans2;
int len,head[maxn];//head[]=-1 
bool Wall[maxn],iscut[maxn];//记录割点
int block_cnt = 0 , cut_cnt = 0;
int dfn[maxn],ti,Low[maxn],col[maxn],Color,fa[maxn],du[maxn];
struct Edge
{
	int to,next;
}e[maxn];
bool vis[maxn];//标记被访问的边和反边 
void Add_Edge(int x,int y){
	//注意len从0起 
	e[len].to = y; e[len].next = head[x]; head[x] = len++;
}
int Point_sum[maxn]; 
bool Point_vis[maxn],cut_vis[maxn];
void Dfs(int x){
	Low[x] = dfn[x] = ++ ti;
	col[x] = -Color;
	Point_sum[Color] ++ ;
	for(int i = head[x] ; i != -1 ; i = e[i].next){
		if(!vis[i]){
			vis[i] = 1;
			vis[i^1] = 1;
			int p = e[i].to;
			if(!col[p]){
				du[x] ++ ;
				fa[p] = x;
				Dfs(p);
				Low[x] = min(Low[p],Low[x]);
			}
			else if(col[p] < 0){
				Low[x] = min(Low[x],dfn[p]);	
			}	
		}	
	}
	col[x] = Color;
}
void Dfs2(int x){
	Point_vis[x] = 1;
	block_cnt ++ ;
	for(int i = head[x] ; i != -1 ; i = e[i].next){
		int p = e[i].to;
		if(!Point_vis[p]){
			if(iscut[p]){
				if(!cut_vis[p]) cut_cnt ++ ; 
				cut_vis[p] = 1;
			}
			else Dfs2(p);	
		}	
	}	
}
void Work(){
	/*  建边  */
	len = 0;
	Mem(head,-1); 
	Mem(Wall,0);
	T = 0;
	Mem(Point_sum,0);
	for(int i = 1 ; i <= m ; i ++ ){
		int x,y; 
		read(x,y);
		T = max(T,max(x,y));
		Wall[x] = Wall[y] = 1;
		Add_Edge(x,y);
		Add_Edge(y,x);	
	}	
	/*  DFS 求割点  */
	ti = 0;
	Color = 0;
	Mem(dfn,0);
	Mem(col,0);
	Mem(Low,0);
	Mem(vis,0);
	Mem(fa,0);
	Mem(du,0);
	for(int i = 1 ; i <= T ; i ++ ){
		if(!Wall[i]) continue;
		if(!col[i]){
			fa[i] = 0;
			Color ++ ;
			Dfs(i);	
		}	
	}
	Mem(iscut,0);
	for(int i = 1 ; i <= T ; i ++ ){
		if(!Wall[i]) continue;
		if(!fa[i] && du[i] >= 2){
			iscut[i] = 1;	
		}
		if(fa[i]){
			if(fa[fa[i]]!=0 && Low[i] >= dfn[fa[i]]){
				iscut[fa[i]] = 1;	
			}	
		}
	}
	int cut_sum = 0;
	for(int i = 1 ; i <= T ; i ++ ){
		if(iscut[i]) cut_sum ++;	
	}
	ans1 = 0;
	ans2 = 1;
	if(cut_sum == 0){
		//整张图强连通
		for(int i = 1 ; i <= Color ; i ++ ){
			ans1 += 2;
			ans2 *= (LL)((LL)(Point_sum[i]-1)*(LL)Point_sum[i]/2);	
		}
		return;	
	}
	/*  对非割点 DFS  */
	Mem(Point_vis,0);
	ans1 = 0;
	ans2 = 1;
	for(int i = 1 ; i <= T ; i ++ ){
		if(!Wall[i]) continue;
		if(!iscut[i] && !Point_vis[i]){
			block_cnt = 0;
			cut_cnt = 0;
			Mem(cut_vis,0);
			Dfs2(i);
			if(cut_cnt == 1){
				ans1 ++ ;
				ans2 *= (LL)(block_cnt);	
			}
		}
	}
}
int main(){
	freopen("bzoj_2730.in","r",stdin);
	freopen("bzoj_2730.out","w",stdout);
	while(scanf("%d",&m) == 1){
		if(!m) break;
		Work();	
		printf("Case %d: ",++Case);
		printf("%lld %lld\n",ans1,ans2);
	}
	getchar(); getchar();
	fclose(stdin); fclose(stdout);
	return 0;
}
/*
6
1 2
1 3
2 3
2 4
2 5
4 5
4
1 2
1 3
2 4 
4 3
5
1 2
2 4
2 3
3 4
4 5
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
4
1 2
1 3
1 4
3 5
0

2
1 2
3 4

4
1 2
2 3
1 3
4 5
*/