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
90
91
92
93
94
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1005;
int cnt=0,n,m,Dfn[maxn],Lowlink[maxn],step=0,Son=0,Mark[maxn],Belong[maxn],BCC=0,cut=0,ans1=0;
LL ans2=1,num=0;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Tarjan(int Now,int father) {
step++;
Dfn[Now]=Lowlink[Now]=step;
for(int Next:edges[Now]) {
if(Next==father)continue;
if(!Dfn[Next]) {
Tarjan(Next,Now);
Lowlink[Now]=min(Lowlink[Next],Lowlink[Now]);
if(Lowlink[Next]>=Dfn[Now]) {
if(Now==1)Son++;
else if(!Mark[Now])Mark[Now]=1;
}
} else Lowlink[Now]=min(Dfn[Next],Lowlink[Now]);
}
}
void Dfs(int Now) {
Belong[Now]=BCC;
if(Mark[Now])return;
num++;
for(int Next:edges[Now]) {
if(Mark[Next]&&Belong[Next]!=BCC) {
cut++;
Belong[Next]=BCC;
}
if(!Belong[Next])Dfs(Next);
}
}
int main() {
while(true) {
m=Get_Int();
if(!m)break;
for(int i=0; i<=n; i++)edges[i].clear();
n=Son=BCC=ans1=step=0;
ans2=1;
memset(Mark,0,sizeof(Mark));
memset(Belong,0,sizeof(Belong));
memset(Dfn,0,sizeof(Dfn));
memset(Lowlink,0,sizeof(Lowlink));
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
n=max(n,max(x,y));
}
Tarjan(1,-1);
if(Son>1)Mark[1]=1;
for(int i=1; i<=n; i++)
if(!Belong[i]&&!Mark[i]) {
BCC++;
cut=num=0;
Dfs(i);
if(!cut) {
ans1+=2;
ans2*=num*(num-1)/2;
} else if(cut==1) {
ans1++;
ans2*=num;
}
}
printf("Case %d: %d %lld\n",++cnt,ans1,ans2);
}
return 0;
}
|
