[HNOI2012] 矿场搭建

/*

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 ;

}