记录编号	578433	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 矿场搭建	最终得分	100
用户昵称	数声风笛ovo	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-03-16 18:35:52	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7;
struct e{
	int u,v,next;
}edge[maxn];
int cnt=0,head[maxn];
void add(int from, int to){
	edge[++cnt].u=from;
	edge[cnt].v=to;
	edge[cnt].next=head[from];
	head[from]=cnt;
	return ;
}
int timex=0,dfn[maxn],low[maxn],cp[maxn]={0};
bool vis[maxn]={0};
stack <int> sta;
void tarjan(int u,int fa){
	dfn[u]=low[u]=++timex;
	sta.push(u); vis[u]=true;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa) continue;
		if(!dfn[v]){
			tarjan(v,u); low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]) cp[u]++;
		}
		else{
			if(vis[v]) low[u]=min(low[u],dfn[v]);
		}
	}
	return ;
}
ll siz=0ll,cpnum=0ll;
void dfs(int u,int col){
	dfn[u]=1; siz+=1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(cp[v] && dfn[v]<col){
			cpnum++; 
			dfn[v]=col;
			continue;
		}
		if(!dfn[v]) dfs(v,col);
	}
	return ;
}
int m,n,ccase=0;
void init(){
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(vis,0,sizeof(vis));
	memset(cp,0,sizeof(cp));
	memset(head,0,sizeof(head));
	cnt=0; timex=0; n=-114514,cpnum=0;
}
int main(){
	freopen("bzoj_2730.in","r",stdin);
	freopen("bzoj_2730.out","w",stdout);
	while(scanf("%d",&m)!=EOF && m!=0){
		init(); ccase++;
		for(int i=1;i<=m;i++){
			int u,v; scanf("%d%d",&u,&v);
			add(u,v); add(v,u);
			n=max(n,max(u,v));
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i]) tarjan(i,i),cp[i]--; 
		}
		for(int i=1;i<=n;i++){
			if(cp[i]>0) cpnum++;
		}
		ll ans1=0ll,ans2=1ll;
		if(cpnum==0){
			ans1=2ll; ans2=(n-1ll)*n/2ll;
		}
		else{
			memset(dfn,0,sizeof(dfn));
			for(int i=1;i<=n;i++){
				cpnum=0ll;
				if(!dfn[i] && !cp[i]){
					siz=0ll; dfs(i,i);
				}
				if(cpnum==1) ans1++,ans2*=siz;
			}
		}
		printf("Case %d: %lld %lld\n",ccase,ans1,ans2);
	}
	return 0;
}