/*codevs 1996 连通性问题Tarjan+割点 可以感性的想一想 一定炸割点最好否则 没有什么影响 先求出割点来对于剩下的点们 缩一下 当然不能包括割点这里的缩 因为删了割点就不是纯粹的双连通分量了所以Dfs缩点 不走割点 然后这张图就成了一些被割点分开的联通块如果一个块块连着两个割点 那么这里面就不用建因为一边的炸了可以走另一边 相对的如果这个块块只连着一个割点那么就必须建一个 位置随便如果没有连着割点的话 就在内部选两个 */#include#include #include #include #define ll long long#define maxn 510using 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< <