/* 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=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';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=0;cnt=1;topt=0;sum=0;num=0;n=0; memset(head,-1,sizeof(head)); memset(size,0,sizeof(size)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(matc,0,sizeof(matc)); memset(f,0,sizeof(f)); memset(r,0,sizeof(r)); memset(c,0,sizeof(c)); } void Dfs(int u,int from){ dfn[u]=low[u]=++topt;int x=0; for(int i=head[u];i!=-1;i=e[i].pre){ int v=e[i].v; if((i^1)==from)continue; if(!dfn[v]){ x++;Dfs(v,i);low[u]=min(low[u],low[v]); if(low[v]>=dfn[u])c[u]=1; } else low[u]=min(low[u],dfn[v]); } if(from<0&&x==1)c[u]=0; } void dfs(int x){ f[x]=1;size[sum]++; for(int i=head[x];i!=-1;i=e[i].pre){ int v=e[i].v; if(f[v])continue; if(c[v]==0)dfs(v); else if(matc[v]!=sum){ matc[v]=sum;r[sum]++; } } } int main() { while(1){ m=init();int u,v; if(m==0)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=1;i<=n;i++) if(dfn[i]==0)Dfs(i,-1); for(int i=1;i<=n;i++) if(c[i]==0&&f[i]==0){ sum++;dfs(i); } if(sum==1){ ans=2;cnt=cnt*(ll)n*(n-1)/2; } else { for(int i=1;i<=sum;i++) if(r[i]==1){ ans++;cnt=cnt*(ll)size[i]; } } printf("Case %d: %d ",++cas,ans);cout<<cnt<<endl; } return 0; }