#include <bits/stdc++.h>
using namespace std;
const int N=1e5;
vector<int> g1[N],g2[N];
bool vis[N];
int dfn[N],n,m,low[N],times,Belong[N],scc_cnt,par[N][21],dep[N],dis[N];
stack<int> st;
void tarjan(int u,int fa){
	vis[u]=1;
	dfn[u]=low[u]=++times;
	st.push(u);
	for(int v:g1[u]){
		if(v==fa) continue;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int v;
		++scc_cnt;
		do{
			v=st.top();
			st.pop();
			Belong[v]=scc_cnt;
			vis[v]=0;
		}while(v!=u);
	}
}
void dfs(int u,int fa){
	par[u][0]=fa;
	dis[u]=dis[fa]+1;
	dep[u]=dep[fa]+1;
	for(int i=1; (1<<i)<=dep[u]; i++) par[u][i]=par[par[u][i-1]][i-1];
	for(int v:g2[u]){
		if(v==fa) continue;
		dfs(v,u);
	}
}
int lca(int u,int v){
	if(dep[u]>dep[v]) swap(u,v);
	int ans=0;
	for(int i=17; i>=0; i--){
		if(dep[u]+(1<<i)<=dep[v]) v=par[v][i];
	}
	if(u==v) return v;
	for(int i=17; i>=0; i--){
		if(par[u][i]==par[v][i]) continue;
		u=par[u][i],v=par[v][i];
	}
	return par[u][0];
}
int main(){
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		int u,v;
		cin>>u>>v;
		g1[u].push_back(v);
		g1[v].push_back(u);
	}
	for(int i=1; i<=n; i++){
		if(!dfn[i]) tarjan(i,0);
	}
	for(int i=1; i<=n; i++){
		for(int j:g1[i]){
			if(Belong[i]!=Belong[j]) g2[i].push_back(j);
		}
	}
	dfs(Belong[1],0);
	int q;
	cin>>q;
	while(q--){
		int u,v;
		cin>>u>>v;
		u=Belong[u],v=Belong[v];
		int lc=lca(u,v);
		int ans=dis[u]+dis[v]-2*dis[lc]+1;
		string s="";
		while(ans){
			s=char(ans%2+'0')+s;
			ans/=2;
		}
		cout<<s<<"\n";
	}
	return 0;
}