RT，第一组数据IDE16KB，交上去就全M

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
stack<ll> s;
int n,m,cnt,cntn;
int dfn[N],low[N],de[N],tp[N],fa[N],bs[N],sz[N];
struct Graph{
	int nt[N<<1],to[N<<1],hd[N],tt;
	Graph(){tt=0;}
	void push(ll u,ll v){
		to[++tt]=v;
		nt[tt]=hd[u];
		hd[u]=tt;
	}
}g,G;
void tarjan(ll u){
	dfn[u]=low[u]=++cnt;
	s.push(u);
	for(int i=g.hd[u];i;i=g.nt[i]){
		ll v=g.to[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				G.push(++cntn,u);
				G.push(u,cntn);
				while(true){
					int tmp=s.top();
					s.pop();
					G.push(cntn,tmp);
					G.push(tmp,cntn);
					if(tmp==v)
						break;
				}
			}
		}
		low[u]=min(low[u],dfn[v]);
	}
}
void dfs1(ll nw,ll en){
	fa[nw]=en;
	sz[nw]=1;
	de[nw]=de[en]+1;
	for(int i=G.hd[nw];i;i=G.nt[i]){
		ll v=G.to[i];
		if(v==en)	continue;
		dfs1(v,nw);
		if(!bs[nw]||sz[bs[nw]]<sz[v])	bs[nw]=v;
		sz[nw]+=sz[v];
	}
}
void dfs2(ll nw,ll top){
	tp[nw]=top;
	if(bs[nw])	dfs2(bs[nw],top);
	for(int i=G.hd[nw];i;i=G.nt[i]){
		ll v=G.to[i];
		if(v==fa[nw]||v==bs[nw])	continue;
		dfs2(v,v);
	}
}
ll lca(ll u,ll v){
	while(tp[u]!=tp[v]){
		if(de[tp[u]]<de[tp[v]])	swap(u,v);
		u=fa[tp[u]];
	}
	if(de[u]<de[v])	swap(u,v);
	return v;
}
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=m;i++){
		ll u,v;
		scanf("%lld %lld",&u,&v);
		g.push(u,v);g.push(v,u);
	}
	cntn=n;
	tarjan(1);
	cnt=0;
	dfs1(1,0);
	dfs2(1,1);
	ll T;scanf("%lld",&T);
	while(T--){
		ll s,t;
		scanf("%lld %lld",&s,&t);
		ll l=lca(s,t);
		printf("%d\n",(de[s]+1)/2+(de[t]+1)/2-(de[l]+1)/2-(de[fa[l]]+1)/2);
	}
	return 0;
}