2014
11-30

# Boonie and Clyde

As two icons of the Great Depression, Bonnie and Clyde represent the ultimate criminal couple. Stories were written, headlines captured, and films were made about the two bank robbers known as Romeo and Juliet in a getaway car.

The new generation of Bonnie and Clyde is no longer cold-blooded killers with guns. Due to the boom of internet, they turn to online banks and scheme to hack the safety system. The safety system consists of a number of computers connected by bidirectional cables. Since time is limited, they decide that they will attack exactly two computers A and B in the network, and as a result, other computers won’t be able to transmit messages via A and B . The attack is considered successful if there are at least two computers (other than A and B ) that disconnected after the attack.

As they want to minimize the risk of being captured, they need to find the easiest way to destroy the safety system. However, a brief study of the network indicates that there are many ways to achieve their objective; therefore they kidnapped the computer expert, you, to help with the calculation. To simplify the problem, you are only asked to tell them how many ways there are to destroy the safety system.

There are multiple test cases in the input file. Each test case starts with two integers N (3<=N<=1000) and M (0<=M<=10000) , followed by M lines describing the connections between the N computers. Each line contains two integers A , B (1<=A, B<=N) , which indicates that computer A and B are connected by a bidirectional cable.

There is a blank line between two successive test cases. A single line with N = 0 and M = 0 indicates the end of input file.

There are multiple test cases in the input file. Each test case starts with two integers N (3<=N<=1000) and M (0<=M<=10000) , followed by M lines describing the connections between the N computers. Each line contains two integers A , B (1<=A, B<=N) , which indicates that computer A and B are connected by a bidirectional cable.

There is a blank line between two successive test cases. A single line with N = 0 and M = 0 indicates the end of input file.

4 4
1 2
2 3
3 4
4 1

7 9
1 2
1 3
2 3
3 4
3 5
4 5
5 6
5 7
6 7

0 0

Case 1: 2
Case 2: 11

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<ctime>
using namespace std;
const int MAX=1005;
struct Bridge{int x,y;}br[1000002];
struct node
{
int v,next;
}g[MAX*MAX];
int set[MAX],num[MAX],bn,D[MAX];
bool cut[MAX];
{
}
void dfs(int u,int fa,int deep)
{
int i,v;
vis[u]=1;
low[u]=D[u]=++index;
int tot=0;
{
v=g[i].v;
if(v==fa||flag[v])
continue;
if(vis[v]!=0)
low[u]=min(low[u],D[v]);
if(vis[v]==0)
{
dfs(v,u,deep+1);
tot++;
low[u]=min(low[u],low[v]);
if((fa==-1&&tot>1)||(fa!=-1&&low[v]>=D[u]))
cut[u]=true;
}
}
vis[u]=2;
}
int find(int x)
{
if(set[x]!=x)
set[x]=find(set[x]);
return set[x];
}
bool check(int x)
{
for(int i=1;i<=n;i++)
{
set[i]=i;
num[i]=1;
}
for(int j=0;j<e;j+=2)
{
if(g[j].v==x||g[j^1].v==x)
continue;
int f1=find(g[j].v);
int f2=find(g[j^1].v);
if(f1==f2)
continue;
else
{
set[f1]=f2;
num[f2]+=num[f1];
}
}
cnt=n-1;
int j=0;
bool ok=false;
for(int i=1;i<=n;i++)
{
int t=find(i);
if(t==i)
j++;
if(num[t]==1&&i!=x)
ok=true;
}
if(j==3)
{
if(ok)
cnt--;
return true;
}
return j>2;
}
void solve()
{
int i,j,k;
int ans=0;
bn=0;
memset(flag,0,sizeof(flag));
for(i=1;i<=n;i++)
{
if(check(i))
{
ans+=cnt;
continue;
}
memset(cut,0,sizeof(cut));
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(D,0,sizeof(D));
index=0;
flag[i]=1;
if(i==1)
dfs(2,-1,0);
else
dfs(1,-1,0);
for(j=1;j<=n;j++)
if(cut[j])
ans++;
flag[i]=0;
}
printf("%d\n",ans/2);
}
int main()
{
int i,j,k;
int ca=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
e=0;
while(m--)
{
scanf("%d%d",&i,&j);
}
printf("Case %d: ",++ca);
if(n<=3)
{
puts("0");
continue;
}
solve();
}
return 0;
}