/*
codevs 1996 连通性问题
Tarjan+割点 可以感性的想一想 一定炸割点最好
否则 没有什么影响 先求出割点来
对于剩下的点们 缩一下 当然不能包括割点
这里的缩 因为删了割点就不是纯粹的双连通分量了
所以Dfs缩点 不走割点
然后这张图就成了一些被割点分开的联通块
如果一个块块连着两个割点 那么这里面就不用建
因为一边的炸了可以走另一边
相对的如果这个块块只连着一个割点那么就必须建一个 位置随便
如果没有连着割点的话 就在内部选两个
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define maxn 510
using namespace std;
int n,m,num,head[maxn],topt,c[maxn],r[maxn],matc[maxn],ans,cas;
int f[maxn],low[maxn],dfn[maxn],sum,size[maxn];
ll cnt;
struct node{
int v,pre;
}e[maxn*maxn];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
void Add(int from,int to){
e[num].v=to;
e[num].pre=head[from];
head[from]=num++;
}
void Cl(){
ans=;cnt=;topt=;sum=;num=;n=;
memset(head,-,sizeof(head));
memset(size,,sizeof(size));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(matc,,sizeof(matc));
memset(f,,sizeof(f));
memset(r,,sizeof(r));
memset(c,,sizeof(c));
}
void Dfs(int u,int from){
dfn[u]=low[u]=++topt;int x=;
for(int i=head[u];i!=-;i=e[i].pre){
int v=e[i].v;
if((i^)==from)continue;
if(!dfn[v]){
x++;Dfs(v,i);low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])c[u]=;
}
else low[u]=min(low[u],dfn[v]);
}
if(from<&&x==)c[u]=;
}
void dfs(int x){
f[x]=;size[sum]++;
for(int i=head[x];i!=-;i=e[i].pre){
int v=e[i].v;
if(f[v])continue;
if(c[v]==)dfs(v);
else if(matc[v]!=sum){
matc[v]=sum;r[sum]++;
}
}
}
int main()
{
while(){
m=init();int u,v;
if(m==)break;Cl();
while(m--){
u=init();v=init();
Add(u,v);Add(v,u);
n=max(n,u);n=max(n,v);
}
for(int i=;i<=n;i++)
if(dfn[i]==)Dfs(i,-);
for(int i=;i<=n;i++)
if(c[i]==&&f[i]==){
sum++;dfs(i);
}
if(sum==){
ans=;cnt=cnt*(ll)n*(n-)/;
}
else {
for(int i=;i<=sum;i++)
if(r[i]==){
ans++;cnt=cnt*(ll)size[i];
}
}
printf("Case %d: %d ",++cas,ans);cout<<cnt<<endl;
}
return ;
}
05-06 02:26