1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}
typedef unsigned long long uLL;
typedef long long LL;
std::vector<int> g[510];
LL ans;
int low[510], dfn[510], b[510];
int cnt, n, q, m, sum1, sum2, tot, t;
bool cut[510];
void tarjan(int x, int p) {
int s = 0;
low[x] = dfn[x] = ++cnt;
for (auto i : g[x]) {
if (!dfn[i]) {
tarjan(i, x);
low[x] = std::min(low[x], low[i]);
if (x != p && low[i] >= dfn[x]) cut[x] = true;
if (x == p) ++s;
}
low[x] = std::min(low[x], dfn[i]);
}
if (x == p && s >= 2) cut[x] = true;
}
void dfs(int x) {
b[x] = t;
if (cut[x]) return ;
++sum2;
for (auto i : g[x]) {
if (cut[i] && b[i] != t) ++sum1, b[i] = t;
if (!b[i]) {
dfs(i);
}
}
}
int main() {
while (std::cin >> m && m) {
cnt = n = t = tot = 0;
ans = 1;
for (int i = 1; i <= 500; ++i) g[i].clear(), low[i] = dfn[i] = b[i] = cut[i] = 0;
for (int i = 1, u, v; i <= m; ++i) {
read(u), read(v);
g[u].push_back(v), g[v].push_back(u);
n = std::max(n, std::max(u, v));
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjan(i, i);
}
}
for (int i = 1; i <= n; ++i) {
if (!b[i] && (!cut[i])) {
++t;
sum1 = sum2 = 0;
dfs(i);
if (!sum1) {
if (sum2 == 1) {
++tot;
ans *= 1;
} else {
tot += 2;
ans *= sum2 * (sum2 - 1) / 2;
}
}
else if (sum1 == 1) ans *= sum2, ++tot;
}
}
printf("Case %d: %d %lld\n", ++q, tot, ans);
}
return 0;
}
|