思路

重点是对于一个VBCC中，整个图的割点有多少个的不同计算。

1.对于有2个及以上全图割点的VBCC

如果坍塌的点是一个割点，此VBCC中的所有矿工肯定可以从别的割点逃到别的VBCC中，从而找到出口。所以不用计算。

2.对于有1个全图割点的VBCC

如果坍塌的点刚好是割点，此VBCC中所有的矿工没法逃往别的VBCC。所以此VBCC中，必须备一个出口。

如果坍塌的是出口，此VBCC中的矿工则可以逃往别的VBCC找出口。所以此VBCC中至少有1个出口。

3.对于没有全图割点的VBCC

由于没有割点，此VBCC中的所有矿工没法逃向任何其他的VBCC。若只备一个出口，如果出口坍塌，矿工无法逃脱。所以一共需要2个以备用。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=10000;

//tarjan 求割点和点双
vector<int>edge[MAXN];	//边
stack<int>stk;			//记录用的栈
int dfn[MAXN];			//时间戳
int low[MAXN];			//可以去的 最上面的 祖先
int tot,vbccnum;		//vbccnum:记录VBCC的数量
vector<int>vbcc[MAXN];	//记录每个VBCC的内容
int invb[MAXN];			//invb[i]:在编号为i的VBCC中，全图割点的数量
bool ap[MAXN];			//记录割点
int ans,many;			//最少放置数和方法数

void tarjan(int x,int root){//记录根，特殊处理
	//初始化
	dfn[x]=low[x]=++tot;
	stk.push(x);
	int son=0;//记录儿子数量（size里可能有非树边）
	
	for(int i:edge[x]){
		if(dfn[i]){//非树边
			low[x]=min(low[x],dfn[i]);
			continue;//防止下面造成死递归
		}
		
		son++;
		tarjan(i,root);//树边
		low[x]=min(low[x],low[i]);
		
		if(low[i]>=dfn[x]){//去别的点的路径依赖于这个点（没法跳过）
			//说明这个点是一个VBCC的分割点
			//有可能是割点，且这个点一定是此VBCC的一个点
			vbcc[++vbccnum].emplace_back(x);
			
			if(x!=root||son>=2){
				//x不是root：父亲和儿子依赖自己
				//大于2个儿子：是根也有2个依赖
				ap[x]=1;
			}
			
			int y;
			do{
				y=stk.top();
				stk.pop();
				vbcc[vbccnum].emplace_back(y);
			}while(y!=i);//x可能属于多个VBCC，不能扔
		}
	}
}

void solve(int T){//第几个情况
	int n=0,m;
	many=1;
	cin>>m;
	
	if(m==0){//结束标志
		exit(0);
	}
	
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		n=max({n,u,v});
		edge[u].emplace_back(v);
		edge[v].emplace_back(u);
	}
	
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i,i);
	}
	
	//计算invb
	for(int i=1;i<=vbccnum;i++){
		for(int j:vbcc[i])if(ap[j])invb[i]++;
		
		if(invb[i]>=2){//此VBCC中有超过1个全图割点
			//从任意全局割点割开，都可以从别的全局割点前往其他VBCC
			//所以不用放，也不作为一种可能性
		}
		else if(invb[i]==1){//此VBCC中刚好有1个全图割点
			//如果从全局割点割开，此VBCC中的矿工会被困住
			//所以必须放置，有size-1种方法
			ans++;
			many*=vbcc[i].size()-1;
		}
		else{//此VBCC中没有全图割点
			//此VBCC中，如果塌陷的是出口，会没法出去
			//所以需要2个出口
			ans+=2;
			many*=vbcc[i].size()*(vbcc[i].size()-1)/2;
		}
	}
	
	cout<<"Case "<<T<<": "<<ans<<" "<<many<<endl;
	
	//恢复原状
	for(int i=1;i<=n;i++)edge[i].clear();
	for(int i=1;i<=vbccnum;i++)vbcc[i].clear();
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	memset(invb,0,sizeof invb);
	memset(ap,0,sizeof ap);
	tot=vbccnum=ans=0;
	many=1;
}

signed main(){
	int t=0;
	while(1)solve(++t);
}