记录编号	578436	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 矿场搭建	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-03-16 21:53:22	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
struct node{
    int n;
    node *nxt;
    node(int n){
        this->n=n;
        nxt=NULL;
    }
    node(){
        nxt=NULL;
    }
}head[550],*tail[550];
int dfn[550],low[550],cnt=0;
int n,m;
bool del[550];
void tarjan(int x,int from){
    int son=0;
    dfn[x]=++cnt;
    low[x]=dfn[x];
    node *p=&head[x];
    while(p->nxt!=NULL){
        p=p->nxt;
        if(dfn[p->n]){
        	low[x]=min(low[x],dfn[p->n]);
		}
        else{
            son++;
            tarjan(p->n,x);
            low[x]=min(low[x],low[p->n]);
            if(from!=0&&low[p->n]>=dfn[x]){
            	del[x]=true;
			}
            if(from==0&&son>1){
            	del[x]=true;
			}
        }
    }
}
bool app[550];
unsigned long long sum=0;
int num=0,w=0;
bool used[550];
bool flag;
void dfs(int x){
    w++;
    node *p=&head[x];
    while(p->nxt!=NULL){
        p=p->nxt;
        if(used[p->n]){
        	continue;
		}
        if(del[p->n]){
            flag=true;
            continue;
        }
        used[p->n]=true;
        dfs(p->n);
    }
    return;
}
int main(){
	freopen("bzoj_2730.in","r",stdin);
	freopen("bzoj_2730.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
    int u,v,t=0;
	cin>>m;
    while(m!=0){
        t++;
        cnt=0;
        n=0;
        num=0;
        sum=1;
        memset(app,0,sizeof(app));
        memset(del,0,sizeof(del));
        memset(dfn,0,sizeof(dfn));
        memset(used,0,sizeof(used));
        for(int i=1;i<=544;i++){
        	tail[i]=&head[i];
		}
        for(int i=1;i<=m;i++){
            cin>>u>>v;
            app[u]=true;
            app[v]=true;
            if(u>n){
            	n=u;
			}
            if(v>n){
            	n=v;
			}
            tail[u]->nxt=new node(v);
            tail[u]=tail[u]->nxt;
            tail[v]->nxt=new node(u);
            tail[v]=tail[v]->nxt;
        }
        for(int i=1;i<=n;i++){
        	if(!dfn[i]){
        		tarjan(i,0);
			}
		}
        for(int i=1;i<=n;i++){
            if(del[i]&&app[i]){
                used[i]=true;
                node *p=&head[i];
                while(p->nxt!=NULL){
                    p=p->nxt;
                    if(!del[p->n]&&!used[p->n]){
                        w=0;
                        used[p->n]=true;
                        flag=0;
                        dfs(p->n);
                        if(!flag){
                            num++;
                            sum*=w;
                        }

                    }
                }
                used[i]=false;
            }
        }
        if(num==0){
            num=2;
            if(n-1==m){
            	sum=2;
			}
            else{
            	sum=n*(n-1)/2;
			}
        }
        cout<<"Case "<<t<<": "<<num<<" ";
        cout<<sum<<endl;
        cin>>m;
    }
    return 0;
}