思路与算法

用带边号的lowlink找割点。删除全部割点后遍历每个非割连通块，记录其相邻割点集合：没有割点邻居时整个原图无割点，需在块内选两个出口，方案C(size,2)；只有一个割点邻居时须在块内选一个出口，贡献size种；至少两个时不需额外出口。

正确性说明

叶端非割块与外部只通过唯一割点连接，该点坍塌后块内必须有出口，选一个也足够。多割点相邻块在一个割点坍塌后仍可从另一方向到某个叶块出口。无割点的连通图删任一顶点仍连通，但出口本身也可能坍塌，所以必须且只需两个。各块选点互不冲突，方案数相乘。

复杂度

每组实际出现的V个点、E≤500条边，编号映射O(ElogV)，DFS与块遍历O(V+E)，割点邻接集合插入O(ElogV)，总O((V+E)logV)时间，O(V+E)空间；初始化同阶。

易错点

输入没声明所有1至最大编号都存在，只统计实际端点。DFS根只有多于一个孩子才是割点，父边按编号跳过以支持重边。方案数使用无符号64位，按题目保证小于2^64。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, cas = 0;
    while (cin >> m && m) {
        map<int, int> ids;
        vector<pair<int, int>> es(m);
        for (auto &e : es) {
            cin >> e.first >> e.second;
            ids[e.first];
            ids[e.second];
        }
        int n = 0;
        for (auto &x : ids)
            x.second = n++;
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < m; i++) {
            int u = ids[es[i].first], v = ids[es[i].second];
            g[u].push_back({v, i});
            g[v].push_back({u, i});
        }
        vector<int> tin(n), low(n), cut(n);
        int tim = 0;
        function<void(int, int)> dfs = [&](int u, int pe) {
            tin[u] = low[u] = ++tim;
            int children = 0;
            for (auto e : g[u])
                if (e.second != pe) {
                    int v = e.first;
                    if (!tin[v]) {
                        children++;
                        dfs(v, e.second);
                        low[u] = min(low[u], low[v]);
                        if (pe != -1 && low[v] >= tin[u])
                            cut[u] = 1;
                    } else
                        low[u] = min(low[u], tin[v]);
                }
            if (pe == -1 && children > 1)
                cut[u] = 1;
        };
        dfs(0, -1);
        vector<int> seen(n);
        unsigned long long ways = 1;
        int need = 0;
        for (int rt = 0; rt < n; rt++)
            if (!cut[rt] && !seen[rt]) {
                vector<int> st(1, rt);
                set<int> border;
                seen[rt] = 1;
                for (int j = 0; j < (int)st.size(); j++)
                    for (auto e : g[st[j]]) {
                        int v = e.first;
                        if (cut[v])
                            border.insert(v);
                        else if (!seen[v]) {
                            seen[v] = 1;
                            st.push_back(v);
                        }
                    }
                if (border.empty()) {
                    need += 2;
                    ways *= st.size() * (st.size() - 1ULL) / 2;
                } else if (border.size() == 1) {
                    need++;
                    ways *= st.size();
                }
            }
        cout << "Case " << ++cas << ": " << need << ' ' << ways << '\n';
    }
}