记录编号	577044	评测结果	AAAAAAAAAA
题目名称	[HDOJ 3686]交通实时查询系统	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.095 s
提交时间	2022-10-21 23:21:31	内存使用	13.72 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=20000+5;
const int M=200000+5;
struct sdf{
	int fr,to,next,id;
}eg[2*M],eg2[4*M];
int head[N],ne=1,head2[2*N],ne2=1;
void add(int x,int y,int opt,int id){
	if (opt==1)eg[++ne]={x,y,head[x],id},head[x]=ne;
	else eg2[++ne2]={x,y,head2[x],id},head2[x]=ne2;
}
int n,m;
int dfn[N],low[N],tim=0;
int st[2*M],tp=0,cnt=0,tot;
bool isge[N]={0},vis[2*M];
int id[2*M];
vector<int>p[N],be[N];
void tarjan(int pt){
	dfn[pt]=low[pt]=++tim;
	int num=0;
	for (int i=head[pt];i!=0;i=eg[i].next){
		if (vis[i])continue;
		int v=eg[i].to;
		vis[i]=vis[i^1]=1;
		st[++tp]=i;
		if (!dfn[v]){
			tarjan(v);
			low[pt]=min(low[pt],low[v]);
			if (dfn[pt]<=low[v]){
				num++;
				if (pt!=1||num>1)isge[pt]=1;
				cnt++;
				int now;
				do{
					int t=st[tp];
					be[eg[t].fr].push_back(cnt);
					be[eg[t].to].push_back(cnt);
					id[eg[t].id]=cnt;now=eg[t].fr;
					tp--;
				}while(now!=pt);
			}
		}
		else low[pt]=min(low[pt],dfn[v]);
	}
	return ;
}
int anc[2*N][30],d[2*N],f[2*N],lgn;
void dfs(int pt,int fa){
	for (int i=head2[pt];i!=0;i=eg2[i].next){
		int v=eg2[i].to;
		if (v==fa)continue;
		anc[v][0]=pt;d[v]=d[pt]+1;
		f[v]=f[pt]+(v>cnt);
		dfs(v,pt);
	}
	return ;
}
int lca(int x,int y){
	if (d[x]<d[y])swap(x,y);
	for (int i=lgn;i>=0;i--){
		if (anc[x][i]!=0&&d[anc[x][i]]>=d[y])x=anc[x][i];
		if (x==y)return x;
	}
	for (int i=lgn;i>=0;i--){
		if (anc[x][i]!=anc[y][i]){
			x=anc[x][i];y=anc[y][i];
		}
	}
	return anc[x][0];
}
int main(){
	freopen ("traffic_query.in","r",stdin);
	freopen ("traffic_query.out","w",stdout);
	while(scanf("%d%d",&n,&m)!=EOF){
		if (n*m==0)return 0;
		memset(head,0,sizeof(head));ne=1;
		memset(head2,0,sizeof(head2));ne2=1;
		memset(isge,0,sizeof(isge));
		memset(vis,0,sizeof(vis));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(id,0,sizeof(id));cnt=tim=0;
		for (int i=1;i<=n;i++)be[i].clear();
		for (int i=1;i<=m;i++){
			int x,y;scanf("%d%d",&x,&y);
			add(x,y,1,i);add(y,x,1,i);
		}	
		tarjan(1);
		tot=cnt;
		for (int i=1;i<=n;i++){
			if (!isge[i])continue;
			sort(be[i].begin(),be[i].end());
			tot++;
			add(be[i][0],tot,2,i);add(tot,be[i][0],2,i);
			for (int j=1;j<be[i].size();j++){
				if (be[i][j]!=be[i][j-1]){
					add(be[i][j],tot,2,i);add(tot,be[i][j],2,i);
				}
			}
		}
		lgn=1.0*log(tot)/log(2);
		d[1]=1;f[1]=0;dfs(1,1);
		for (int i=1;i<=lgn;i++){
			for (int j=1;j<=tot;j++)anc[j][i]=anc[anc[j][i-1]][i-1];
		}
		int q;scanf("%d",&q);
		while(q--){
			int x,y;scanf("%d%d",&x,&y);
			int posx=id[x],posy=id[y];
			int l=lca(posx,posy);
			printf("%d\n",f[posx]+f[posy]-2*f[l]+(l>cnt));
		}
		for (int i=1;i<=cnt;i++)p[i].clear();
	}
	return 0;
}