做法：
利用tarjan算法求出每一个节点出现时对应的时间戳dfn。
对于每一个桥，恰有一个节点与其对应。
isb[i]标记i之前的边是不是桥。
当连接两点的时候，求出这两个点到根节点的路径上的边，把这些边的isb设置成0；
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define MAXN 500001
using namespace std;
struct list
{
int u;
int v;
int next;
}node[MAXN];
int head[MAXN],vis[MAXN];
int isb[MAXN];
int nums;
int fa[MAXN];
int n,m,cnt;
int dfn[MAXN],low[MAXN],index;
void init()
{
nums=0;
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
for(int i=0;i<=n;i++)fa[i]=i;
cnt=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(isb,0,sizeof(isb));
index=0;
}
void add(int x,int y)
{
node[nums].u=x;
node[nums].v=y;
node[nums].next=head[x];
head[x]=nums++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++index;
for(int i=head[u];i!=-1;i=node[i].next)
{
if(vis[i])continue;
vis[i]=vis[i^1]=1;
int v=node[i].v;
if(!dfn[v])
{
fa[v]=u;
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
{
cnt++;
isb[v]=1;
}
}
else
{
low[u]=min(low[u],dfn[v]);
}
}
}
void LCA(int x,int y)
{
while(x!=y)
{
if(isb[x])cnt--,isb[x]=0;
if(isb[y])cnt--,isb[y]=0;
x=fa[x];
y=fa[y];
}
}
int main()
{
int x,y;
int cas=0;
while(~scanf("%d%d",&n,&m)&&(n||m))
{
cas++;
init();
while(m--)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
tarjan(1);
printf("Case %d:\n",cas);
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&x,&y);
LCA(x,y);
cout<<cnt<<endl;
}
cout<<endl;
}
}