|
- #include <cstdio>
- #include <cstring>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int n,cnt,low[20009],flag[20009],num[20009],root,m,ans,gedian,book[20009],t,hahaha=0,ansx=0;
- long long u;
- vector <int> e[20009];
- void dfs(int cur,int father)
- {
- int child=0,i;
- cnt++;
- num[cur]=cnt;
- low[cur]=cnt;
- for(i=0;i<e[cur].size();i++)
- {
- int v = e[cur][i];
- if(num[v]==0)
- {
- child++;
-
- dfs(v,cur);
- low[cur] = min(low[cur],low[v]);
- if(cur!=root && low[v]>=num[cur])
- {
- flag[cur]=1;
- }
- if(cur==root && child>=2)
- {
- flag[cur]=1;
- }
- }
- else
- {
- if(v!=father)
- {
- low[cur]=min(low[cur],num[v]);
- }
- }
- }
- return;
- }
- void use(int v)
- {
- if(book[v]==t)
- {
- return;
- }
- book[v]=t;
- if(flag[v]==1)
- {
- gedian++;
- return;
- }
- ans++;
- for(int x=0;x<e[v].size();x++)
- {
- use(e[v][x]);
- }
- return;
- }
- int main()
- {
- int i,j;
- while(scanf("%d",&m) && m!=0)
- {
-
- cnt=0;
- memset(flag,0,sizeof(flag));
- memset(book,0,sizeof(book));
- memset(low,0,sizeof(low));
- memset(num,0,sizeof(num));
- gedian=0;
- ans=0;
- t=-1;
- n=0;
- u=1;
- for(i=1;i<=m;i++)
- {
- int a,b;
- scanf("%d%d",&a,&b);
- n=max(a,n);
- n=max(b,n);
- e[a].push_back(b);
- e[b].push_back(a);
- }
- for(i=1;i<=n;i++)
- {
- if(num[i]==0)
- {
- root=i;
- dfs(root,root);
- }
- }
- u=1;
- for(i=1;i<=n;i++)
- {
- if(book[i]==0 && flag[i]!=1)
- {
- use(i);
- t--;
- if(gedian==1)
- {
- ansx++;
- u=u*ans;
- }
- ans=0;
- gedian=0;
- }
- }
- hahaha++;
- int h;
- h=n*(n-1)/2;
- if(ansx==0)
- {
- printf("Case %d: 2 %d\n",hahaha,h);
- }
- else
- {
- printf("Case %d: %d %lld\n",hahaha,ansx,u);
- }
-
- ansx=0;
- for(i=1;i<=n;i++)
- {
- e[i].clear();
- }
- }
- return 0;
- }
复制代码 |
|