惨不忍睹

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7;
const int M=5e4+7;
struct Graph1{
	struct edge{
		int nxt,v;
	}e[N];
	int h[N],cnt;
	inline void add_edge(int u,int v){
		e[++cnt].nxt=h[u],e[cnt].v=v;
		h[u]=cnt;
	}
	int dfn[N],low[N],tot,st[N],top,belong[N],x;
	inline void Tarjan(int u,int fa){
		dfn[u]=low[u]=++tot;
		st[++top]=u;
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(v==fa) continue;
			if(!dfn[v]){
				Tarjan(v,u);
				low[u]=min(low[u],low[v]);
			}else low[u]=min(low[u],dfn[v]);
		}
		if(low[u]==dfn[u]){
			int v;x++;
			do belong[v=st[top--]]=x; while(u!=v);
		}
	}
}G1;
struct Gragh2{
	int n;
	struct edge{
		int nxt,v;
	}e[N];
	int h[N],cnt;
	inline void add_edge(int u,int v){
		e[++cnt].nxt=h[u],e[cnt].v=v;
		h[u]=cnt;
	}
	int fa[N][16];
	int dep[N];
	inline void dfs(int u,int _fa){
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(v==_fa) continue;
			dep[v]=dep[u]+1;fa[v][0]=u;
			dfs(v,u);
		}
	}
	inline void init(){
		for(int i=1;i<=15;i++)
			for(int j=1;j<=n;j++)
				fa[j][i]=fa[fa[j][i-1]][i-1];
	}
	inline int LCA(int x,int y){
		if(dep[x]<dep[y]) swap(x,y);
		if(x==y) return x;
		for(int i=15;i>=0;i--)
			if(dep[fa[x][i]]>=dep[y])
				x=fa[x][i];
		if(x==y) return x;
		for(int i=15;i>=0;i--)
			if(fa[x][i]!=fa[y][i])
				x=fa[x][i],y=fa[y][i];
		return fa[x][0]; 
	}
}G2;
int n,m,q,a,b;
int u[N],v[N];
inline void print(int u){
	int tmp[20]={0};int cnt;
	while(u) tmp[++cnt]=u&1,u>>=1;
	while(cnt) putchar(tmp[cnt--]?'1':'0');
	putchar('\n');
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u[i],&v[i]);
		G1.add_edge(u[i],v[i]),G1.add_edge(v[i],u[i]);
	}
	for(int i=1;i<=n;i++) if(!G1.dfn[i]) G1.Tarjan(i,0);
	for(int i=1;i<=m;i++){
		u[i]=G1.belong[u[i]],v[i]=G1.belong[v[i]];
		if(u[i]!=v[i]){
			G2.add_edge(u[i],v[i]);
			G2.add_edge(v[i],u[i]);
		}
	}
	G2.n=G1.x;G2.dep[1]=1;G2.dfs(1,0);
	G2.init();
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&a,&b);a=G1.belong[a],b=G1.belong[b];
		print(G2.dep[a]+G2.dep[b]-G2.dep[G2.LCA(a,b)]*2+1);
	}
	return 0;
}