#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
struct Node{
	int next,to,from;
}a[N],b[N];
int ans[N],bq,n,m,head[N],tot,noj,dfn[N],low[N],timestamp,ins[N],tt,s[N],belong[N],tot1,head1[N],d[N],f[N][21],val[N];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void add(int u,int v){
	a[++tot].to=v;
	a[tot].from=u;
	a[tot].next=head[u];
	head[u]=tot;
}
void add1(int u,int v){
	b[++tot1].to=v;
	b[tot1].from=u;
	b[tot1].next=head1[u];
	head1[u]=tot1;
}
void dfs(int u,int fa){
	dfn[u]=low[u]=++timestamp;
	ins[u]=1;
	s[++tt]=u;
	for(int i=head[u];i;i=a[i].next){
		int v=a[i].to;
		if(!dfn[v]){
			dfs(v,i);
			low[u]=min(low[u],low[v]);
		}else if(i!=(fa^1))low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int y;
		while(y=s[tt--]){
			belong[y]=u;
			ins[y]=0;
			if(y==u)break;
			val[u]+=1;
		}
	}
}
void ddfs(int u,int fa){
	d[u]=d[fa]+val[u];
	f[u][0]=fa;
	for(int i=1;(1<<i)<=d[u];i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=head1[u];i;i=b[i].next){
		int v=b[i].to;
		if(v!=fa){
			ddfs(v,u);
		}
	}
}
int lca(int u,int v){
	if(d[u]>d[v])swap(u,v);
	for(int i=20;i>=0;i--){
		if(d[u]<=d[v]-(1<<i)){
			v=f[v][i];
		}
	}
	if(u==v)return u;
	for(int i=20;i>=0;i--){
		if(f[u][i]==f[v][i])continue ;
		else u=f[u][i],v=f[v][i];
	}
	return f[u][0];
} 
void anns(int x){
	bq=0;
	memset(ans,0,sizeof(ans));
	while(x){
		ans[++bq]=x%2;
		x/=2;		
	}
	for(int i=bq;i>=1;i--){
		cout<<ans[i];
	}
	cout<<endl;
}
signed main(){
	cin>>n>>m;
	tot=1;
	for(int i=1;i<=m;i++){
		int u,v;
		u=read(),v=read();
		add(u,v);
		add(v,u);
	} 
	fill(val+1,val+n+1,1);
	for(int i=1;i<=n;i++){
		if(!dfn[i])dfs(i,0);
	}
	for(int i=1;i<=m;i++){
		int x=belong[a[i].from],y=belong[a[i].to];
		if(x!=y){
			add1(x,y);
		}
	}
	ddfs(1,0);
	cin>>noj;
	while(noj--){
		int u,v;
		u=read(),v=read();
		u=belong[u],v=belong[v];
		anns(d[u]+d[v]-d[lca(u,v)]-d[f[lca(u,v)][0]]);
	}
	return 0;
}
/*
图上如何用LCA算出两点的距离 
d(u,v)=d(u,root)+d(v,root)-d(lca(u,v),0) 
but if 有点权,要用容斥原理，原式-上一个d(fa(lca(u,v)),0); 




*/