缩点完之后直接暴跳 LCA ， 也可以过，注释掉的是树链剖分

//
/*
Author : Zmonarch
Knowledge :
*/
#include <bits/stdc++.h>
#define inf 2147483647
#define int long long
using namespace std ;
const int kmaxn = 1e6 + 10 ;
int read() {
	int x = 0 , f = 1 ; char ch = getchar() ;
	while(!isdigit(ch)) {if(ch == '-') f = - 1 ; ch = getchar() ;}
	while( isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar() ;}
	return x * f ;
}
struct node {
	int nxt , u , v ; 
}e[kmaxn]; 
int n , m , Tp , idx , cnt , tot ; 
int h[kmaxn] , dfn[kmaxn] , low[kmaxn] , id[kmaxn] , son[kmaxn] , siz[kmaxn] , pre[kmaxn];
int scc[kmaxn] , top[kmaxn] , sta[kmaxn] , in[kmaxn] , f[kmaxn] , dep[kmaxn];
vector <int> E[kmaxn] ;  
void add(int u , int v) {
	e[++tot].nxt = h[u] ; 
	e[tot].v = v ; e[tot].u = u ; 
	h[u] = tot ;
}
void Add(int u , int v) {
	E[u].push_back(v) ;
}
void Tarjan(int u , int fa) {
	low[u] = dfn[u] = ++ idx ; sta[++Tp] = 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 if(!in[v]) low[u] = min(low[u] , dfn[v]) ; 
	}
	if(low[u] == dfn[u]) 
	{
		++ cnt ; 
		while(true) 
		{
			int tmp = sta[Tp] ; Tp-- ; 
			scc[tmp]++ ; in[tmp] = cnt ; 
			if(tmp == u) break ; 
		} 	
	} 
}
//void dfs1(int u , int fa) {
//	f[u] = fa ; dep[u] = dep[fa] + 1 ; siz[u] = 1 ; 
//	for(int i = 0 ; i < E[u].size() ; i++) 
//	{
//		int v = E[u][i] ; 
//		if(v == fa) continue ; 
//		dfs1(v , u) ; siz[u] += siz[v] ; 
//		if(siz[son[u]] < siz[v]) son[u] = v ; 
//	}
//}
//void dfs2(int u , int ftop) {
//	top[u] = ftop ; id[u] = ++ idx ; pre[idx] = u ; 
//	if(son[u]) dfs2(son[u] , ftop) ; 
//	for(int i = 0 ; i < E[u].size() ; i++) 
//	{
//		int v = E[u][i] ; 
//		if(v == f[u] || v == son[u]) continue ; 
//		dfs2(v , v) ;
//	}
//}
void DFS(int u , int fa) {
	dep[u] = dep[fa] + 1 ; f[u] = fa ; 
	for(int i = 0 ; i < E[u].size() ; i++)
	{
		int v = E[u][i] ; 
		if(v == fa) continue ; 
		DFS(v , u) ; 
	}
} 
//int LCA(int u , int v) {
//	while(top[u] ^ top[v]) 
//	{
//		if(dep[top[u]] < dep[top[v]]) swap(u , v) ; 
//		u = f[top[u]] ;  
//	}
//	return dep[u] < dep[v] ? u : v ; 
//}
int LCA(int u , int v) {
	while(u ^ v) 
	{
		if(dep[u] < dep[v]) swap(u , v) ; 
		u = f[u] ; 
	}
	return dep[u] < dep[v] ? u : v ;  
}
void PAns(int x) {
	static int a[32] ; int cnt = 0 ; 
	while(x != 0) a[++cnt] = x % 2ll , x /= 2ll ; 
	if(cnt)
	{
		for(int i = cnt ; i ; i--) printf("%lld" , a[i]) ;
	}	
	else printf("%d" , 0) ; 
	printf("\n") ; 
}
void Ans_Query(int u , int v) {
	int lca = LCA(u , v) ; 
	PAns(dep[u] + dep[v] - 2 * dep[lca] + 1) ; 
}
signed main(){
	n = read() , m = read() ; 
	for(int u , v , i = 1 ; i <= m ; i++)
	 u = read() , v = read() , add(u , v) , add(v , u) ; 
	for(int i = 1 ; i <= n ; i++) if(!dfn[i]) Tarjan(i , 0) ; 	
	for(int i = 1 ; i <= n ; i++) 
	{
		for(int j = h[i] ; j ; j = e[j].nxt) 
		{
			int v = e[j].v ;
			if(in[i] != in[v]) Add(in[i] , in[v]); 
		}
	}
	idx = 0 ;
	m = read() ; 
	DFS(1 , 0) ; 
	//dfs1(1 , 0) ; dfs2(1 , 1) ; 
	for(int u , v , i = 1 ; i <= m ; i++) 
	 u = read() , v = read() , Ans_Query(in[u] , in[v]) ; 
	return 0 ;
}