题目描述

每组输入第一行一个整数,代表后面出现的条路径。给出这样的一个无向图，如果你可以放置逃生通道在容易一个点处，也可以放置任意数量的逃生通道，现在询问最少的逃生通道个数是几个，并且保证通道个数最少的情况下，有几种放置方案使得全部人在图中随机某个点消失的情况下也可以顺利逃生。

。

居然给出的是一个无向图那么分类讨论。
1、首先独立的点一定是需要独立的逃生通道的，因为它不与外界任何点连边，只能从自己出去或者自己消失。
2、这里题目明示了点塌陷，那么图论中与点消失有关的就是割点了。往割点一靠你就会找到规律。再去掉独立点的情况下，如果一个连通块中不存在割点，也就是独立在其他点之外，这样的连通块，我们一定要安排2个逃生通道，因为如果只安排一个，可能这个点塌陷了，那么其他的点无法去到外界也无法找到逃生通道了，那么对可选择的方案数就是，假设连通块中点数量为。
3、如果我们用割点把图给切割了，那么你会找到，如果是1个割点的图它一定要在割点左边放一个右边放一个，才能保证个数最少，那么就是。如果有2个割点呢？你会挑一个逃生通道放在中间的位置嘛？显然不会那么笨，如果你放在中间并且只打算放2个的话，那么说明左边或者右边一定有一个地方是没有逃生通道的，那么如果没有通道的一变割点消失，就有一边没有成功撤离了。如果打算放3个是一定可以的，但是我们需要3个嘛？不需要，我们只需要不放在中间，一直往两边放即可，如果中间某个点断开可以沿着路径去到另外联通的逃生通道。问题就得到解决了。那么再看3个割点4个割点都是一样的情况，可选择的方案数就是。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 500 + 7;

int head[N], tot;
struct Node {
    int v, nxt;
}edge[N << 1];
void add(int u, int v) {
    edge[++tot].v = v;
    edge[tot].nxt = head[u];
    head[u] = tot;
}

int rt, dfn[N], low[N], cnt, boo[N];
void tarjan(int u) { // 求割点
    dfn[u] = low[u] = ++cnt;
    int son = 0;
    for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ++son;
                if (u != rt or son > 1)    boo[u] = 1;
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

int vis[N], cnt1, cnt2;
unordered_set<int> st;
void bfs(int x) {
    st.clear();
    queue<int> q;
    q.push(x);
    while (q.size()) {
        int u = q.front();    q.pop();
        if (vis[u])    continue;
        vis[u] = 1;
        ++cnt2;
        for (int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].v;
            if (vis[v])    continue;
            if (boo[v]) { // 以割点分隔连通块
                st.insert(v);
                continue;
            }
            q.push(v);
        }
    }
}

bool check(int u) {
    for (int i = head[u]; i; i = edge[i].nxt)
        return false;
    return true;
}

void init() {
    ms(head, 0);
    ms(dfn, 0);
    ms(low, 0);
    ms(boo, 0);
    ms(vis, 0);
    cnt = tot = 0;
}

void solve() {
    int m, ca = 0;
    while (m = read()) {
        if (!m)    break;
        init(); // 多组
        int n = 0;
        rep(i, 1, m) {
            int u = read(), v = read();
            add(u, v), add(v, u);
            n = max(n, max(u, v));
        }
        rep(i, 1, n)
            if (!dfn[i])    rt = i, tarjan(i);
        ll ans1 = 0, ans2 = 1;
        rep(i, 1, n) {
            if (check(i)) { // 独立的点一定要放一个通道
                ++ans1;
                continue;
            }
            if (boo[i])    continue; // 是割点不可能再这里放通道，没必要看了
            if (!vis[i]) {  // 没遍历过的连通块
                cnt2 = 0; // 计算除了割点之外有几个点
                bfs(i);
                cnt1 = st.size(); // 有几个割点
                if (cnt1 == 0)
                    ans1 += 2, ans2 *= cnt2 * (cnt2 - 1) / 2;
                else if (cnt1 == 1)
                    ans1 += 1, ans2 *= cnt2;
            }
        }
        printf("Case %d: %lld %lld\n", ++ca, ans1, ans2);
    }
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}