#include<bits/stdc++.h>
using namespace std;
const int N=1e5+55;
int fa[N][30],ans,fr[N],t[N],deep[N],w[N][30];
struct node{
	int pre[N],head[N],to[N],cnt;
	void add(int x,int y){
		pre[++cnt]=head[x];
		head[x]=cnt;
		to[cnt]=y;
	}
}e1,e2;
int dfn[N],dff,tot,low[N],now[N];
bool v[N];
stack <int >s;
void tarjan(int x,int f){
	s.push(x);
	v[x]=1;
	low[x]=dfn[x]=++dff;
	for(int i=e1.head[x];i;i=e1.pre[i]){
		int u=e1.to[i];
		if(u==f)continue;
		if(!dfn[u]){
			tarjan(u,x);
			low[x]=min(low[u],low[x]);
		}
		else{
			if(v[u]){
				low[x]=min(low[x],dfn[u]);
			}
		}
	}
	if(low[x]==dfn[x]){
		tot++;
		while(s.top()!=x){
			int u=s.top();
			s.pop();
			now[u]=tot;
			v[u]=0;
		}
		s.pop();
		now[x]=tot;
		v[x]=0;
	}
}
void dfs(int x,int f){
	fa[x][0]=f;
	deep[x]=deep[f]+1;
	for(int i=1;i<=20;++i){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=e2.head[x];i;i=e2.pre[i]){
		int u=e2.to[i];
		if(u==f) continue;
		dfs(u,x);
	}
}
int _lca(int a,int b){
	if(a==b)return a;
	if(deep[a]>deep[b]) swap(a,b);
	for(int i=20;i>=0;--i){
		if(deep[fa[b][i]]>=deep[a]){
			b=fa[b][i];
		}
	}
	if(a==b) return a;
	for(int i=20;i>=0;--i){
		if(fa[a][i]==fa[b][i])continue;
		a=fa[a][i],b=fa[b][i];
	}
	return fa[a][0];
}
int c[40];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		fr[i]=x,t[i]=y;
		e1.add(x,y);
		e1.add(y,x);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i])	tarjan(i,0);
	}
	for(int i=1;i<=m;++i){
		if(now[fr[i]]!=now[t[i]]){
			e2.add(now[fr[i]],now[t[i]]);
			e2.add(now[t[i]],now[fr[i]]);
		}
	}
	dfs(1,0);
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		int a,b;
		scanf("%d%d",&a,&b);
		int s=deep[a]+deep[b]-2*deep[_lca(a,b)]+1;
		int l=0;
		memset(c,0,sizeof(c));
		while(s){
			c[++l]=s%2;
			s/=2;
		}
		for(int i=l;i>=1;--i){
			printf("%d",c[i]);
		}
		printf("\n");
	}
	return 0;
}