#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+10;
const int M = 6e5+10;
int n,m,u[N],v[N],head[M<<1],q,qx,qy;
int dfn[N],low[N],belong[N],cut[N],tot,cnt=1,edcc;
int lg[N],f[N][30],dep[N];
int num[N];
vector<int>e[N];
map<int,int>p[N];
struct node{
	int u,v,nxt;
}edge[M<<1];
void add(int u,int v){
	edge[++cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
void tarjan(int x,int pre){
	dfn[x]=low[x]=++tot;
	for(int i=head[x];i;i=edge[i].nxt){
		int to=edge[i].v;
		if(i==(pre^1)) continue;
		if(!dfn[to]){
			tarjan(to,i);
			low[x]=min(low[x],low[to]);
			if(low[to]>dfn[x]){
				cut[i]=cut[i^1]=1;
			}
		}else{
			low[x]=min(low[x],dfn[to]);
		}
	}
}
void dfs(int x){
	belong[x]=edcc;
	for(int i=head[x];i;i=edge[i].nxt){
		int to=edge[i].v;
		if(cut[i]||belong[to]) continue;
		dfs(to);
	}
}
void mdfs(int x,int fath){
	f[x][0]=fath,dep[x]=dep[fath]+1;
	for(int i=1;i<=lg[dep[x]];i++) f[x][i]=f[f[x][i-1]][i-1];
	for(int i=0;i<e[x].size();i++){
		int to=e[x][i];
		if(to!=fath){
			mdfs(to,x); 
		}
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]){
		x=f[x][lg[dep[x]-dep[y]]];
	}
	if(x==y) return x;
	for(int k=lg[dep[x]];k>=0;k--){
		if(f[x][k]!=f[y][k]){
			x=f[x][k],y=f[y][k];
		}
	}
	return f[x][0];
}
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*f;
} 
signed main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		u[i]=read();v[i]=read();
		add(u[i],v[i]);add(v[i],u[i]);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	for(int i=1;i<=n;i++){
		if(!belong[i]) edcc++,dfs(i);
	}
	for(int i=1;i<=m;i++){
		int x=belong[u[i]],y=belong[v[i]];
		if(x==y) continue;
		if(p[x][y]) continue;
		e[x].push_back(y);
		e[y].push_back(x);//建树 
		p[x][y]=p[y][x]=1;
	}
	for(int i=1;i<=edcc;i++) lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
	mdfs(1,0);
	q=read();
	while(q--){
		qx=read();qy=read();
		qx=belong[qx];
		qy=belong[qy];
		int lca=LCA(qx,qy);
		int ans=dep[qx]-dep[lca]+dep[qy]-dep[lca]+1;
		int o=0;
		while(ans){
			num[++o]=(ans&1);
			ans>>=1;
		}
		for(int i=o;i>=1;i--) printf("%d",num[i]);
		putchar('\n');
	}
	return 0;
}