#include<bits/stdc++.h>
#define int short
using namespace std;

const int maxn=10001;
const int maxm=50001;

int n,m;

struct E {
	int v,id;
};

struct E2{
	int u,v;
};

vector<E> g[maxn];

unordered_map<int,bool> dis;

int f[maxn][21];

int dfn[maxn], cnt;

int low[maxn],clk,fa[maxn],top,tag[maxn],dcc;



int dep[maxn];

int st[maxn];

void addE(int u,int v) {
	g[u].push_back(E {v,++cnt});
	g[v].push_back(E {u,++cnt});
	return;
}

void tarjan(int u) {
	dfn[u]=++clk;
	low[u]=dfn[u];
	st[++top]=u;
//	printf("%d\n",u);
	for(E vt:g[u]) {
		int v=vt.v;
//		printf("fa[%d]:%d\n",v,fa[v]);
		if(!fa[v]) {
			fa[v]=u;
			tarjan(v);
//			printf("low[%d]:%d\n",v,low[v]);
			if(low[v]>dfn[u]) {
				dis[vt.id]=dis[vt.id+(vt.id%2?1:-1)]=1;
			} else low[u]=low[v];
		}
	}
	if(low[u]==dfn[u]) {
		++dcc;
		while(st[top]!=u) tag[st[top--]]=dcc;
		tag[st[top--]]=dcc;
	}
}

void floodfill(int u,int t) {
	tag[u]=t;
	for(E vt:g[u]) {
		int v=vt.v;
		if(!tag[v]&&!dis.count(vt.id)) {
			floodfill(v,t);
		}
	}
}


vector<E2> e;

vector<int> g2[maxn];

void dfs(int u,int p) {
	dep[u]=dep[p]+1;
	f[u][0]=p;
	for(int i=1; i<=20; i++) f[u][i]=f[f[u][i-1]][i-1];

	for(int v:g2[u]) {
		if(v==p) continue;
		dfs(v,u);
	}
}

int getLca(int u,int v) {
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=20; i>=0; i--) {
		if(dep[f[u][i]]>=dep[v]) {
			u=f[u][i];
		}
	}
	if(u==v) return u;
	for(int i=20; i>=0; i--) {
		if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	}
	return f[u][0];
}

stack<char> s;

// bool lj[maxn][maxn];

main() {
	cin>>n>>m;
	int kkk=dep[-123123];
	for(int i=1; i<=m; i++) {
		int u,v;
		cin>>u>>v;
		addE(u,v);
		e.push_back(E2 {u,v});
	}
	tarjan(1);
	for(int i=1; i<=n; i++) {
		g[i].clear();
		g[i].shrink_to_fit();
	}


	for(E2 ed:e) {
		if(tag[ed.u]==tag[ed.v]) continue;
		g2[tag[ed.u]].push_back(tag[ed.v]);
		g2[tag[ed.v]].push_back(tag[ed.u]);
//		lj[tag[ed.u]][tag[ed.v]]=lj[tag[ed.v]][tag[ed.u]]=1;
	}
	dfs(1,1);
	int T;
	cin>>T;
	while(T--) {
		int a,b;
		cin>>a>>b;
		int lca=getLca(tag[a],tag[b]);
		int p=-dep[lca]*2+dep[tag[a]]+dep[tag[b]]+1;
		while(p>0) {
			s.push('0'+(p&1));
			p>>=1;
		}
		while(!s.empty()) {
			cout<<s.top();
			s.pop();
		}
		cout<<endl;
	}
}