http://poj.org/problem?id=3694

题意就是给一个无向连通图动态加边，对于每次询问输出图中的桥的数量。

考虑先对原图进行缩点求出edcc，然后考虑加边后树上会产生环，然后对于两个点求lca，两个点到lca的路径上的桥就全都不是桥了。

但是写炸了，求条。

//ways:傻逼缩点
//orz aqx wvr zak 
//noip 2024 rp++ 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
//#define ls ch[now][0]
//#define rs ch[now][1]
//#define mid ((x+y)>>1)
//#define checkbug cout << "okok" << endl;
//#define len (r-l+1)
const int maxn=1e5+10;
const int inf=1e9;
const int maxa=2e3+10;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int to[maxn],tot,nxt[maxn],head[maxn];
int head2[maxn],nxt2[maxn],to2[maxn],tot2;
bool bridge[maxn];
int n,m,ans;
void adde(int x,int y){
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void addc(int x,int y){
	to2[++tot2]=y;
	nxt2[tot2]=head2[x];
	head2[x]=tot2;
}
int dfn[maxn],low[maxn],num;
void tarjan(int x,int root){
	dfn[x]=low[x]=++num;
	for(int i=head[x];i;i=nxt[i]){
		int tox=to[i];
		if(!dfn[tox]){
			tarjan(tox,i);
			low[x]=min(low[x],low[tox]);
			if(low[tox]>dfn[x]){
				bridge[i]=bridge[i^1]=1;
				ans++;
			}
		}else if(i!=(root^1)){
			low[x]=min(low[x],dfn[tox]);
		}
	}
}
int dcc;
int c[maxn];
void dfs(int x){
	c[x]=dcc;
	for(int i=head[x];i;i=nxt[i]){
		int tox=to[i];
		if(c[tox]||bridge[i]){
			continue;
		}
		dfs(tox);
	}
}
int dep[maxn];
int fa[maxn][25];
void dfs2(int x,int fax){
	fa[x][0]=fax;
	dep[x]=dep[fax]+1;
	for(int i=0;fa[x][i];i++){
		fa[x][i+1]=fa[fa[x][i]][i];
	}
	for(int i=head2[x];i;i=nxt2[i]){
		int tox=to2[i];
		if(tox!=fax){
			dfs2(tox,x);
		}
	}
}
int lca(int x,int y){
	if(dep[x]>dep[y]){
		swap(x,y);
	}
	for(int i=20;i>=0;i--){
		if(dep[x]<=dep[y]-(1<<i)){
			y=fa[y][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=20;i>=1;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int f[maxn];
int find(int x){
	while(x!=f[x]){
		x=f[x]=f[f[x]];
	}
	return x;
}
void init(){
	memset(bridge,0,sizeof(bridge));
	memset(head,0,sizeof(head));
	memset(head2,0,sizeof(head2));
	for(int i=0;i<=n;i++){
		f[i]=i;
	}
	ans=dcc=num=0;
	tot=tot2=-1;
}
int id=1;
signed main(){
	while((n=read())|(m=read())){
		init();
		for(int i=1;i<=m;i++){
			int x,y;
			cin >>x >> y;
			adde(x,y);
			adde(y,x);
		}
		for(int i=1;i<=n;i++){
			if(!dfn[i]){
				tarjan(i,0);
			}
		}
		for(int i=1;i<=n;i++){
			if(!c[i]){
				++dcc;dfs(i);
			}
		}
		for(int i=0;i<=tot;i++){
			int x=to[i],y=to[i^1];
			if(c[x]==c[y]){
				continue;
			}
			addc(c[x],c[y]);
			addc(c[y],c[x]);
		}
		dfs2(1,0);
		int q;
		cin >> q;
		cout << "Case " << id++ << ":" << endl;
		while(q--){
			int nowx,nowy;
			cin >> nowx >> nowy;
			int x=c[nowx],y=c[nowy];
			int Lca=lca(x,y);
			x=find(x),y=find(y);
			while(dep[x]>dep[Lca]){
				f[x]=find(fa[x][0]);
				x=find(x);
				ans--;
			}
			while(dep[y]>dep[x]){
				f[y]=find(fa[x][0]);
				y=find(y);
				ans--;
			}
			cout << ans << endl;
		}
		cout << endl;
	}
	return 0;
}