#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=1000010;
long long ver[M],nxt[M],head[M],dfn[M],low[N],edge[M],d[M];
long long vc[M],nc[M],hc[M],f[10000][30],tc,t,tt[100000];
bool hh[100000],ins[M];
long long stuck[10000],c[M],ans,ji;
vector<int> scc[M];
long long n,m;
long long num,tot,cnt,top;
queue<int>q;
void add_c(int x,int y){
	 vc[++tc]=y;
	 nc[tc]=hc[x];
	 hc[x]=tc;
}
void bfs(){
    q.push(1); d[1]=1;
    while(q.size()){
        long long x=q.front();q.pop();
        for(int i=hc[x];i;i=nc[i]){
            long long pp=vc[i];
            if(d[pp]) continue;
            d[pp]=d[x]+1;
            f[pp][0]=x;
            for(int j=1;j<=t;j++){
                f[pp][j]=f[f[pp][j-1]][j-1];
            q.push(pp);
            }
        }

    }
}
int lca(int x,int y){
    if(d[x]>d[y]) swap(x,y); 
     for(int i=t;i>=0;i--){
         if(d[f[y][i]]>=d[x]) y=f[y][i];
     }
     if(x==y) return x;
     for(int i=t;i>=t;i--){
         if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

     }return f[x][0];

}
// int search(int ll,int rr,int curr){
// 	 cout<<"ll= "<<ll<<" m="<<m<<endl;
// 	if(!ok){
// 	if(ll<=0||ll>m) return 0;
// 	if(ll!=rr){
//         for(int i=hc[ll];i;i=nc[i]){
// 		cout<<ll<<" "<<rr<<endl;
//         // cout<<edge[c[vc[i]]]<<endl;
// 		//    cout<<vc[i]<<endl;
// 		//    cout<<"c[ver[i]]="<<c[vc[i]]<<endl;
// 		   if(!hh[c[vc[i]]]){
// 			  hh[c[vc[i]]]=1;
// 			  search(vc[i],rr,curr+edge[c[vc[i]]]);
// 			}
// 			else search(vc[i],rr,curr);
//     }
// 	 }
//      else {cout<<"   "<<curr+1<<"A";ok=1;return 0;}
//   }
// }
void tarjan(int x,int fff){
	 dfn[x]=low[x]=++num;
	 stuck[++top]=x;
	 ins[x]=1;
	 for(int i=head[x];i;i=nxt[i]){
	 	int y=ver[i];
		 if(y==fff) continue;
		 if(!dfn[y]){
            tarjan(y,x);
		    low[x]=min(low[x],low[y]);
	 		
	 	}
	 	else if(ins[y])low[x]=min(low[x],dfn[y]);		
	 }
	 if(dfn[x]==low[x]){
	 	cnt++;
		edge[cnt]++;
        int z;
	 	do{
	 	  z=stuck[top--];
	 	  ins[z]=0;
	 	  c[z]=cnt;
	 	  scc[cnt].push_back(z);
	 	}while(x!=z);
	 }
}
void add(int x,int y){
	 ver[++tot]=y;
	 nxt[tot]=head[x];
	 head[x]=tot;
}
void shuchu(int x)//二进制转化
{
    long long xx = 0;
    for(; x; x>>=1)
    {
    	xx ++;
    	if(x & 1) tt[xx] = 1;
    	else tt[xx] = 0;
    }
    for (int i = xx; i >= 1; i--) printf("%d",tt[i]);
    printf("\n");
}
int main(){
   
	cin>>n>>m;
    t=(int)(log(n)/log(2))+1;
    for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		if(u!=v)
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=nxt[i]){
			int gg=ver[i];
			if(c[x]==c[gg]) continue;
			else{add_c(c[x],c[gg]);
			add_c(c[gg],c[x]);}
		}
	}

    
    int ci;
	cin>>ci;
	bfs();
	
	for(int i=1;i<=ci;i++){
       long long x,y;
	   cin>>x>>y;
	   shuchu(d[c[x]]+d[c[y]]-2*d[lca(c[x],c[y])]+1);
	}
	// // cout<<cnt<<" ";
	
	 system("pause");
}