rt，80分

按照SDOI战略游戏的思路，建圆方树，求距离。

可以过P4606，但是这个题T了

可能是我有一些什么奇奇怪怪的锅。/kk

#include<bits/stdc++.h>
using namespace std;
#define R register
const int N=5e6+9;
int bcc[N],cnt_bcc,cut[N],cnt;
vector<int> g[N],G[N];
int fa[N][29],dep[N],low[N],dfn[N],dis[N],ind,n,m,ans;
int stk[N],tp;
int T,S,a[N],x,y,Q;

inline void Tarjan(int u)
{
	dfn[u]=low[u]=++ind;
	stk[++tp]=u;
	for(R int i=0;i<g[u].size();++i)
	{
		int v=g[u][i];
		if(!dfn[v]) 
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]==dfn[u])
			{
				cnt++;
				int x;
				while(1)
				{
					x=stk[tp];
					G[x].push_back(cnt);
					G[cnt].push_back(x);
					tp--;
					if(x==v) break;
				}
				G[u].push_back(cnt);
				G[cnt].push_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}	
}

inline void dfs(int u,int f)
{
	fa[u][0]=f;
	dfn[u]=++ind;
	dep[u]=dep[f]+1;
	dis[u]=dis[f]+(u<=n);
	for(R int i=0;i<19;++i) fa[u][i+1]=fa[fa[u][i]][i];
	for(auto v:G[u]) if(v!=f) dfs(v,u);
}

inline int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(R int i=19;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(R int i=19;i>=0;--i)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}

inline bool cmp(int x,int y){return dfn[x]<dfn[y];}

inline int read(){
	int res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+ch-'0';
		ch=getchar();
	}
	return res*f;
}

int main()
{
	T=1;
	while(T--)
	{
		n=read(),m=read();
		for(R int i=1;i<=m;++i)
		{
			x=read(),y=read();
			g[x].push_back(y);
			g[y].push_back(x);
		}
		cnt=n;
		for(R int i=1;i<=n;++i) if(!dfn[i]) Tarjan(i);
		ind=0;
		memset(dfn,0,sizeof dfn);
		dfs(1,0);
		Q=read();
		while(Q--)
		{
			S=2;
			for(R int i=1;i<=S;i++) a[i]=read();
			sort(a+1,a+1+S,cmp);ans=0;
			for(R int i=1;i<=S;i++)
			{
				int u=a[i],v=a[i+1];
				if(i==S) v=a[1];
				ans+=dis[u]+dis[v]-2*dis[lca(u,v)];
			}
			ans/=2;
			// ans-=S;
			if(lca(a[1],a[S])<=n) ans++;
			printf("%d\n",ans);
		}
	}
	return 0;
}