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

int n, m ;
const int N = 1e5 + 10 ;
int tot ;
int size[N] ;

int e[N], ne[N], h[N], idx ;
int dfs[N], low[N], ti ;
int id[N] ;

bool st[N] ;
int dcc_cnt ;

void add(int a, int b) {
	e[idx] = b ;
	ne[idx] = h[a] ;
	h[a] = idx ++ ;
}
stack <int> s ;

void tarjan(int u, int from) {
	dfs[u] = low[u] = ++ ti ;
	s.push(u) ;
	for (int i = h[u] ; i != -1; i = ne[i]) {
		int j = e[i] ;
		if (!dfs[j]) {
			tarjan(j, i) ;
			low[u] = min(low[u], low[j]) ;
			if (dfs[u] < low[j])
				st[i] = st[i ^ 1] = 1 ;
		} else if (i != (from ^ 1))
			low[u] = min(low[u], dfs[j]) ;
	}

	if (dfs[u] == low[u]) {
		++ dcc_cnt ;
		int y ;
		do {
			y = s.top() ;
			s.pop() ;
			id[y] = dcc_cnt ;
			size[dcc_cnt] ++ ;
		} while (y != u) ;
	}
}

vector <int> v[N] ;

int dist[N] ;
int f[N][20], fe[N] ;

void bfs() {
	queue <int> q ;
	q.push(1) ;
	memset(dist, 0x3f, sizeof dist) ;
	dist[1] = 1, dist[0] = 0 ;

	while (q.size()) {
		int t = q.front() ;
		q.pop() ;

		for (auto u : v[t]) {
			int j = u ;
			if (dist[j] > dist[t] + 1) {
				dist[j] = dist[t] + 1 ;
				q.push(j) ;

				f[j][0] = t ;
				fe[j] = fe[t] + size[j] ;

				for (int k = 1 ; k <= 19 ; k ++)
					f[j][k] = f[f[j][k - 1]][k - 1] ;
			}
		}
	}
}

int lca(int a, int b) {
	if (dist[a] < dist[b])
		swap(a, b) ;

	for (int k = 19 ; k >= 0 ; k --) {
		if (dist[f[a][k]] >= dist[b])
			a = f[a][k] ;
	}

	if (a == b)
		return a ;

	for (int k = 19 ; k >= 0 ; k --) {
		if (f[a][k] != f[b][k]) {
			a = f[a][k], b = f[b][k] ;
		}
	}

	return f[a][0] ;
}



void solve(int ans) {

	if (ans == 0) {
		cout << 0 << endl ;
		return ;
	} else if (ans == 1) {
		cout << 1 << endl ;
		return ;
	}
	vector <int> vv ;
	while (ans) {
		vv.push_back(ans % 2) ;
		ans /= 2 ;
	}

	for (int i = vv.size() - 1 ; i >= 0 ; i --)
		cout << vv[i] ;
	cout << endl ;
}

signed main() {
	cin >> n >> m ;

	memset(h, -1, sizeof h) ;
	for (int i = 1 ; i <= m ; i ++) {
		int a, b;
		cin >> a >> b ;
		if (a == b)
			continue ;
		add(a, b) ;
		add(b, a) ;
	}

	for (int i = 1 ; i <= n ; i ++)
		if (!dfs[i])
			tarjan(i, -1) ;


	for (int i = 1 ; i <= n ; i ++) {
		for (int j = h[i] ; j != -1 ; j = ne[j]) {
			int k = e[j] ;
			int a = id[i], b = id[k] ;
			if (a != b) {
				v[a].push_back(b) ;
				v[b].push_back(a) ;
				//cout << "edge : " << a << ' ' << b << ' ' << size[a] << endl ;
			}
		}
	}

	bfs() ;

	cin >> tot ;

	int ans = 0 ;
	while (tot --) {
		int a, b;
		cin >> a >> b ;
		a = id[a], b = id[b] ;

		int x = lca(a, b) ;

		ans = dist[a] + dist[b] - dist[x] * 2 + 1 ;

		solve(ans) ;
	}
	return 0 ;
}

/*
4 4
1 2
2 3
1 3
1 4
*/