题目大意：有N个矿井 ，由一些隧道连接起来，现在要修建尽量少的安全通道，使得无论哪个矿井发生事故，所有人均能逃出（其实就是问每个点相互到达至少有两条点不重复的路径），求建的最少的安全通道数量和方案数
解题思路：建安全通道的话，肯定不能建在割顶，因为割顶如果崩塌了，割顶所连接的双连通分量内的点就跑不掉了，还得在双连通分量里面再建点(上述为双连通分量内部只有一个割顶的情况)，这样不划算，还不如直接在里面建点
如果一个双连通分量的内部割顶有多个的话，那么在这个双连通分量里面就可以不用建安全通道了，因为一个割顶崩塌了，还有其他点可以连向外面，所以，只考虑内部只有一个割顶的双连通分量要怎么建安全通道
怎么建呢，排除掉割顶的所有的点都可以建
假设ans1代表所需要建立的安全通道的数量，ans2代表建立的方案数，那么找到内部只有一个割顶的双连通分量时(双连通分量的内部结点有n个,排除掉割顶的话，还有n-1种建立的方案)
那么ans1 = ans1 + 1; ans2 *= (n - 1)
如果给的图形成的是一个双连通分量（假设有n个点），只有一个，那么需要建立2个安全通道(一个倒塌了，还有另一个),方案数为n * (n - 1) / 2
求解点双连通分量与边双连通分量其实和求解割点与桥密切相关。不同双连通分量最多只有一个公共点，即某一个割顶，任意一个割顶都是至少两个点双连通的公共点。不同边双连通分量没有公共点，而桥不在任何一个边双连通分量中，点双连通分量一定是一个边双连通分量。
下面首先介绍点双连通分量的Tarjan算法：
在之前的博客中，我们已经知道如何求解割顶了，很容易可以发现，当我们找到割顶的时候，就已经完成了一次对某个极大点双连通子图的访问，那么我们如果在进行DFS的过程中将遍历过的点保存起来，是不是就可以得到点双连通分量了？为了实现算法，我们可以在求解割顶的过程中用一个栈保存遍历过的边（注意不是点！因为不同的双连通分量存在公共点即割顶），之后每当找到一个点双连通分量，即子结点v与父节点u满足关系low[v]>=dfn[u]，我们就将栈里的东西拿出来直到遇到当前边。
这里注意放入栈中的不是点，而是边，这是因为点双连通分量是存在重复点的，如果我们放入栈中的是点，那么对于某些点双连通分量，就会少掉一些点（这些点都是割顶）。
板子：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int maxe = 1e5 + 5;
int n, m, dfs_cnt, bcc_cnt, dfn[maxn], low[maxn], cut[maxn], bccno[maxn];
vector<int> v[maxn], bcc[maxn];
struct node
{
int u, v;
node(){}
node(int uu, int vv) : u(uu), v(vv){}
}edge[maxe];
stack<node> sta;
void tarjan(int x, int f)
{
int son = 0;
dfn[x] = low[x] = ++dfs_cnt;
for(int i = 0; i < v[x].size(); i++)
{
int to = v[x][i];
node e = node(x, to);
if(!dfn[to])
{
sta.push(e), son++;
tarjan(to, x);
low[x] = min(low[x], low[to]);
if(low[to] >= dfn[x])
{
cut[x] = 1;
bcc[++bcc_cnt].clear();
while(1)
{
node t = sta.top();
sta.pop();
if(bccno[t.u] != bcc_cnt)
{
bcc[bcc_cnt].push_back(t.u);
bccno[t.u] = bcc_cnt;
}
if(bccno[t.v] != bcc_cnt)
{
bcc[bcc_cnt].push_back(t.v);
bccno[t.v] = bcc_cnt;
}
if(t.u == x && t.v == to)
break;
}
}
}
else if(dfn[to] < dfn[x] && to != f)
{
sta.push(e); //存边
low[x] = min(low[x], dfn[to]);
}
}
if(f < 0 && son == 1)
cut[x] = 0;
}
void get_bcc(int x)
{
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(cut, 0, sizeof(cut));
memset(bccno, 0, sizeof(bccno));
dfs_cnt = bcc_cnt = 0;
for(int i = 1; i <= x; i++)
if(!dfn[i])
tarjan(i, -1);
}
int main()
{
int ca = 1;
while(~scanf("%d", &n), n)
{
for(int i = 0; i < maxn; i++)
v[i].clear();
int x, y, tot = 0;
for(int i = 0; i < n; i++)
{
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
tot = max(tot, x);
tot = max(tot, y);
}
get_bcc(tot);
ll ans1 = 0, ans2 = 1;
for(int i = 1; i <= bcc_cnt; i++)
{
int cut_cnt = 0;
for(int j = 0; j < bcc[i].size(); j++)
{
if(cut[bcc[i][j]])
cut_cnt++;
}
if(cut_cnt == 1)
{
ans1++;
ans2 *= (ll)(bcc[i].size()-1);
}
}
if(bcc_cnt == 1)
{
ans1 = 2;
ans2 = (ll)bcc[1].size() * (bcc[1].size()-1) / 2;
}
printf("Case %d: %lld %lld\n", ca++, ans1, ans2);
}
return 0;
}