#include<bits/stdc++.h>
#define mxn 400005
using namespace std;
int dfn[mxn], low[mxn], col[mxn], lt[mxn], rt[mxn], dis[mxn];
int n, m, q, a1, a2, cnt;
bool vis[mxn];
unordered_map<int, vector<int> > G, NG;
stack<int> s;
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++cnt;
	s.push(u);
    for (auto v : G[u]){
        if (v == fa)
			continue;
        if (!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                vis[v] = 1;
            } 
        } else 
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        col[u] = u;
        while (s.top() != u){
        	col[s.top()] = u;
			s.pop();
		}
        s.pop();
    }
}
int spfa(int s, int t){
	memset(dis, -1, sizeof dis);
	queue<int> q;
	q.push(s);
	dis[s] = 0;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		for (auto v : NG[u])
			if (dis[v] == -1 || dis[v] > dis[u] + 1){
				dis[v] = dis[u] + 1;
				q.push(v);
			}
	}
	return dis[t];
}
void bin(int x){
	stack<int> S;
	while (x){
		S.push(x & 1);
		x >>= 1;
	}
	while (!S.empty()){
		cout << S.top();
		S.pop();
	}
	cout << "\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[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 (auto v : G[i]){
			if (col[i] == col[v])
				continue;
			NG[col[i]].push_back(col[v]);
			NG[col[v]].push_back(col[i]);
		}
	}
	cin >> q;
	while (q--){
		int s, t;
		cin >> s >> t;
		bin(spfa(s, t) + 1);
	}
}