待二刷
/*
给一个不一定连通的无向图
问最少在几个点设置出口
使得任意一个出口坏掉后,其他所有点都可以和某个出口连通

首先考虑
1 出口数量>=2 如果只有一个出口 那这个出口坏了就没有可以用的出口了
2 不同连通块之间相互独立(最终方案数 = 各连通块方案数乘积)
  对一个连通块
  2.1 无割点 <=> 不管我删掉哪个点 图剩余部分都是连通的、且剩余好出口>=1
             <=> 度数==0 
             <=> 孤立的点
      那么我们必须设置2个出口就可以满足
      连通块中点个数=cnt
      方案数=C[cnt][2] = cnt*(cnt-1)/2
  2.2 有割点 <=> 点双连通分量 缩点(每个割点都属于2个点双连通分量)
        2.2.1 先将所有割点单独出来作为一个点
        2.2.2 从每个点双连通分量(V-DCC)向其所包含的每个割点连一条边
     o       o
    / \     / \
   o---.---.---o 
        \ /
         o
    缩完点后 .-割点  o-连通块
    o-.-o-.-o  同时缩完后的o中包含之前有连的
        2.2.3 看V-DCC度数
            2.2.3.1 如果V-DCC==1 意味着它只包含一个割点(上图中左和右)
            则如果这个割点是出口且坏掉 这个V-DCC就无法连到其他出口了
            🔺所以V-DCC==1 时 必须在V-DCC内(非割点)放置一个出口
            2.2.3.2 如果V-DCC>1
            就不需要设置出口

证明:
1 如果割点坏了
    缩完点后,🔺此时所有度数==1的点相当于一个叶子节点-所有度数为1的叶子节点放一个出口
    因此每个叶子节点必然会有一个出口
        .(割点)
      ×/ \×   
      o   o(连通块)    
2 如果度数为1的右边的V-DCC里的某个点坏了
    由于是V-DCC 删去坏点后仍然是一个V-DCC
        .(割点)
       / \   
      o   @(连通块中坏了一个点)
    但此时不影响这个V-DCC到割点 并通过割点到左边V-DCC中的出口
3 如果度数为2的V-DCC里的某个点坏了
    由于度数==2 <=> 必然连接两个割点
        o(连通块)
       / \
      .   .(割点) 
    每个割点必然有一个出口
    所以可以从上面的o到下面的两个割点到其他V-DCC找到出口
总结:
1 无割点          放2个出口 方案数 *= C[cnt][2] = cnt*(cnt-1)/2
2 有割点 V-DCC==1 放1个出口 方案数 *= C[cnt-1][1] = cnt-1 (不包含割点)
3 有割点 V-DCC>=2 放0个出口 方案数 *= 1
*/

#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 1010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++timestamp;
    stk[++top] = u;
    // 1 u是孤立点-自称一个dcc
    if(u==root && h[u]==-1)//u是根节点且没有邻边
    {
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }
    // 2 u不孤立
    int cnt = 0;
    for(int i = h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u],low[j]);
            // 看j是不是能连到比u还高的地方
            if(dfn[u]<=low[j])//j最高比u高度低 说明j是u一个新的分支(如果把u删掉 多一个j连通块)
            {
                cnt++;
                // 判断u是否割点 如果不是根节点-只要有一个分支他就是割点 || 如果是根节点 需要有两个分支才是割点
                //    root            /
                //    / \          非root(自带上面一个边,所以只要一个下分支)
                //                   /
                if(u!=root||cnt>1)cut[u] = true;
                ++dcc_cnt;
                int y;
                do{
                    y = stk[top--];
                    dcc[dcc_cnt].push_back(y);
                }while(y!=j);//注意弹出栈不是弹到u为止 而是弹到j为止(u仍保留在stk中)
                // 🔺 开新分支 == u一定和新分支j组成一个dcc 也和旧连通块组成dcc
                // 那么当前最高点u还要被用在更高的包含u的旧连通块
                // 所以如果这个时候出栈了 回溯到比u高的点的时候 u就加不进旧连通块里
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u],dfn[j]);
    }
}

int main()
{
    int T = 1;
    while(cin >> m,m)
    {
        for(int i=1;i<=dcc_cnt;i++)dcc[i].clear();
        idx = n = timestamp = top = dcc_cnt = 0;
        memset(h,-1,sizeof h);
        memset(dfn,0,sizeof dfn);
        memset(cut,0,sizeof cut);
        while(m--)
        {
            int a,b;
            cin >> a >> b;
            n = max(n,b),n = max(n,a);//第二个n=漏了
            add(a,b),add(b,a);
        }

        for (root = 1; root <= n; root ++ )
            if (!dfn[root])
                tarjan(root);

        int res = 0;
        ULL num = 1;
        for(int i = 1;i<=dcc_cnt;i++)
        {
            int cnt = 0;
            for(int j= 0;j<dcc[i].size();j++)//j< 写成了i<
            {
                if(cut[dcc[i][j]])
                    cnt++;
            }
            // 无割点
            if(cnt == 0)//cnt写成了cut
            {
                if(dcc[i].size()>1)res+=2,num*=dcc[i].size()*(dcc[i].size()-1)/2;
                else res++;
            }
            else if(cnt==1)res++,num*=dcc[i].size()-1;
        }
        printf("Case %d: %d %llu\n", T ++, res, num);
    }
    return 0;
}