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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
struct edge{
int u,v,nxt;
}e[maxn<<2];
int cnt=0,h[maxn];
void add(int u,int v){
e[++cnt]=(edge){u,v,h[u]};
h[u]=cnt;
}
int dfn[maxn],low[maxn],vis[maxn],flag[maxn],tot=0,rt;
void tarjan(int u,int fa){
int son=0;
dfn[u]=low[u]=++tot;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(dfn[v]==0){
son++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) flag[u]=1;
}
else if(v!=fa){
low[u]=min(dfn[v],low[u]);
}
}
if(u==rt&&son==1){
flag[u]=0;
}
}
int m,u,v,n,num,cut,col,casessss=0;
unsigned long long ans1,ans2;
void init(){
cnt=0;tot=0;col=0;n=0;
ans1=0;ans2=1;
memset(h,0,sizeof(h));
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(flag,0,sizeof(flag));
}
void dfs(int u){
vis[u]=col;
num++;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(flag[v]&&vis[v]!=col){
cut++;
vis[v]=col;
}
if(!vis[v]) dfs(v);
}
}
int main(){
while(scanf("%d",&m)){
if(m==0) break;
casessss++;
init();
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
n=max(n,u);
n=max(n,v);
}
rt=1;
for(int i=1;i<=n;i++){
if(!dfn[i]) rt=i,tarjan(rt,-1);
}
for(int i=1;i<=n;i++){
if(!vis[i]&&!flag[i]){
col++;
num=cut=0;
dfs(i);
if(cut==0){
ans1+=2;
ans2*=(num-1)*num/2;
continue;
}
if(cut==1){
ans1+=1;
ans2*=num;
continue;
}
}
}
printf("Case %d: %lld %lld\n",casessss,ans1,ans2);
}
return 0;
}
|
