#include<bits/stdc++.h>
#define N 10005
#define M 100005
using namespace std;
int n,m,t,i,k,l,a[M],b[M],cnt,num,u[M];
int low[N],dfn[N],in[N],rem[N],h[N];
int f[N][20],v[N];
bool op[N][N];
stack<int> s;
struct qwq{
	int b,n;
}d[M];
void cun(int a,int b){
	d[++k].b=b;
	d[k].n=h[a],h[a]=k;
}
void Tarjan(int a){
	dfn[a]=low[a]=++num;
	in[a]=1,s.push(a);
	int i,b;
	for(i=h[a];i;i=d[i].n){
		if(u[i]) continue;
		b=d[i].b;
		u[i-!(i&1)]=u[i+(i&1)]=1;
		if(!dfn[b]){
			Tarjan(b);
			low[a]=min(low[a],low[b]);
		}
		else if(in[b]) low[a]=min(low[a],dfn[b]);
	}
	if(low[a]==dfn[a]){
		cnt++;
		do{
			b=s.top();
			in[b]=0,s.pop();
			rem[b]=cnt;
		}while(a!=b);
	}
}
void print(int n){
	if(!n) return;
	print(n>>1);
	putchar(n&1|'0');
}
void dfs(int a,int p){
	int i,b;
	for(i=h[a];i;i=d[i].n){
		b=d[i].b;
		if(b==p) continue;
		v[b]=v[a]+1;
		dfs(b,f[b][0]=a);
	}
}
int lca(int a,int b){
	if(a==b) return a;
	if(v[a]<v[b]) swap(a,b);
	int i;
	for(i=15;i>=0;i--)
		if(v[a]-v[b] & 1<<i)
			a=f[a][i];
	if(a==b) return a;
	for(i=15;i>=0;i--)
		if(f[a][i]!=f[b][i])
			a=f[a][i],b=f[b][i];
	return f[a][0];
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		++l;
		scanf("%d%d",&a[l],&b[l]);
		if(a==b || op[a[l]][b[l]] || op[b[l]][a[l]]){
			l--;
			continue;
		}
		cun(a[l],b[l]);
		cun(b[l],a[l]);
		op[a[l]][b[l]]=op[b[l]][a[l]]=1;
	}
	for(i=1;i<=n;i++){
		if(!dfn[i]){
			num=0;
			Tarjan(i);
		}
	}
	memset(h,0,sizeof(h));
	k=0;
	for(i=1;i<=l;i++){
		if(rem[a[i]]==rem[b[i]]) continue;
		cun(rem[a[i]],rem[b[i]]);
		cun(rem[b[i]],rem[a[i]]);
	}
	dfs(1,0);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		n=rem[n],m=rem[m];
		k=lca(n,m);
		print(v[n]+v[m]-v[k]*2+1);
		puts("");
	}
	return 0;
}

LCA+Tarjan马蜂极好，求大佬解惑