做法是给边双连通分量缩点，然后用树剖求LCA

#include<stdio.h>
#include<bits/stdc++.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

const int N=1e4+5,M=1e5+5;
int n,m,u,v,a,b,tot,id,cnt,edges=1;
int head[N],dfn[N],low[N],belong[N],fa[N],son[N],h[N],size[N],top[N];
struct edge{
	int v,next;
	bool ban;
}e[M];
vector<int>g[N];
map<pair<int,int>,bool>link;

inline void add(int u,int v)
{
	e[++edges]=(edge){v,head[u],false};
	head[u]=edges;
}

void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++id;
	for(register int i=head[u];i;i=e[i].next)
		if(!dfn[e[i].v])
		{
			tarjan(e[i].v,u);
			low[u]=min(low[u],low[e[i].v]);
			if(low[e[i].v]>dfn[u]) e[i].ban=e[i^1].ban=true;
		}
		else if(fa!=e[i].v) low[u]=min(low[u],dfn[e[i].v]);
}

void DFS(int u,int id)
{
	belong[u]=id;
	for(register int i=head[u];i;i=e[i].next)
		if(!e[i].ban&&!belong[e[i].v]) DFS(e[i].v,id);
}

void DFS1(int u,int p)
{
	fa[u]=p,size[u]=1,h[u]=h[p]+1;
	for(register int i=0;i<g[u].size();++i)
		if(g[u][i]!=p)
		{
			DFS1(g[u][i],u);
			size[u]+=size[g[u][i]];
			if(size[g[u][i]]>size[son[u]]) son[u]=g[u][i];
		}
}

void DFS2(int u,int t)
{
	top[u]=t;
	if(son[u]) DFS2(son[u],t);
	for(register int i=0;i<g[u].size();++i)
		if(g[u][i]!=son[u]&&g[u][i]!=fa[u]) DFS2(g[u][i],g[u][i]);
}

inline int LCA(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(h[top[u]]<h[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	return h[u]<h[v]?u:v;
}

void print(int res)
{
	if(res>>1) print(res>>1);
	printf("%d",res&1);
}

int main(void)
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	tarjan(1,0);
	for(register int i=1;i<=n;++i)
		if(!belong[i]) DFS(i,++cnt);
	for(register int i=1;i<=n;++i)
		for(register int j=head[i];j;j=e[j].next)
			if(belong[i]!=belong[e[j].v]&&!link[make_pair(min(belong[i],belong[e[j].v]),max(belong[i],belong[e[j].v]))])
			{
				link[make_pair(min(belong[i],belong[e[j].v]),max(belong[i],belong[e[j].v]))]=true;
				g[belong[i]].push_back(belong[e[j].v]);
				g[belong[e[j].v]].push_back(belong[i]);
			}
	DFS1(1,0),DFS2(1,1);
	scanf("%d",&tot);
	while(tot--)
	{
		scanf("%d%d",&a,&b);
		print(h[belong[a]]+h[belong[b]]-(h[LCA(belong[a],belong[b])]<<1)+1);
		putchar('\n');
	}
	return 0;
}