Luogu

分析

可以发现，在一个点双联通分量中，设割点的数目为 $s_1$，非割点的数目为 $s_2$，那么：

• 若 $s_1=0$，即没有割点，那么要有两个出口才能保证能出去。此时出口可以放在任意两个非割点上。
• 若 $s_1=1$，即只有一个割点，那么如果割点坍塌就都出不去了，所以要放一个出口。此时出口可以放在任意一个非割点上。注意到这里若非割点坍塌，其它点可以通过割点离开到其它分量去。
• 若 $s_1>1$，即有大于一个割点，那么无论哪个点坍塌，其它点都可以到别的分量去。此时不用设置出口。

于是只要把割点和点双求出来即可。

代码

#include <bits/stdc++.h>
#define re register
#define max_(a,b) ((a)>(b)?(a):(b))
#define min_(a,b) ((a)<(b)?(a):(b))
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m;

struct Edge { int v,nxt; };
Edge e[1010];
int head[510],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int dfn[510],low[510],dfs_clock=0;
int cut[510];

inline void Tarjan(int u,const int root) {
    dfn[u]=low[u]=++dfs_clock; int f=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v,root);
            low[u]=min_(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                f++;
                if (u!=root||f>1) cut[u]=1;
            }
        }
        else low[u]=min_(low[u],dfn[v]);
    }
}

int vis[510],dfs_time=0;
int sc=0,snc=0; //割点数、非割点数 

inline void Dfs(int u) {
    vis[u]=dfs_time,++snc;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (vis[v]==dfs_time) continue;
        if (cut[v]) ++sc,vis[v]=dfs_time;
        else Dfs(v);
    }
}

mainint main() {
    int T=0;
    while (m=read()) {
        if (!m) break;

        n=cnt=dfs_time=dfs_clock=0;
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(vis));
        memset(low,0,sizeof(vis));
        memset(head,0,sizeof(head));
        memset(cut,0,sizeof(head));

        for (re int i=1;i<=m;++i) {
            int x=read(),y=read();
            addEdge(x,y);
            addEdge(y,x);
            n=max_(n,max_(x,y));
        }

        for (re int i=1;i<=n;++i)
            if (!dfn[i]) Tarjan(i,i);

        int ans1=0,ans2=1;
        for (re int i=1;i<=n;++i) {
            if (vis[i]||cut[i]) continue;
            ++dfs_time,sc=0,snc=0;
            Dfs(i);
            if (!sc) ans1+=2,ans2*=snc*(snc-1)/2;
            else if (sc==1) ++ans1,ans2*=snc;
        }
        printf("Case %lld: %lld %lld\n",++T,ans1,ans2);
    }
    return 0;
}