#include<bits/stdc++.h>
#define MAXN 10010
#define MAXM 50010
using namespace std;
struct edge{
    int pre, to;
};
int n, m, cnt = 1, idx, tot, root;
int head[MAXN], dfn[MAXN], low[MAXN], col[MAXN], fa[MAXN][20], dep[MAXN];
bool iscut[MAXM << 1], vis[MAXN];
stack<int> s;
edge e[MAXM << 1];
vector<int> g[MAXN];
pair<int, int> eg[MAXM];
void add_edge(int u, int v){
    e[++cnt].pre = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
void tarjan(int now, int from){
    low[now] = dfn[now] = ++idx; s.push(now);
    for(int i = head[now]; i; i = e[i].pre){
        if(i == (from ^ 1)) continue;
        if(!dfn[e[i].to]){
            tarjan(e[i].to, i);
            low[now] = min(low[now], low[e[i].to]);
        }else if(dfn[e[i].to] < low[now]) low[now] = dfn[e[i].to];
    }
    if(dfn[now] == low[now]){
        tot++;
        while(!s.empty() && s.top() != now){
            col[s.top()] = tot;
            s.pop();
        }
        col[s.top()] = tot; s.pop();
    }
}
void bfs(int root){
    queue<int> q;
    q.push(root);
    vis[root] = true; dep[root] = 0;
    while(!q.empty()){
        int now = q.front(); q.pop();
        int siz = g[now].size();
        vis[now] = true;
        for(int i = 0; i < siz; i++){
            if(vis[g[now][i]]) continue;
            dep[g[now][i]] = dep[now] + 1;
            fa[g[now][i]][0] = now;
            q.push(g[now][i]);
        }
    }
}
int get_lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    int maxi = 0;
    while((1 << maxi) < dep[x]) maxi++;
    maxi--;
    for(int i = maxi; i >= 0; i--){
        if(dep[x] - (1 << i) >= dep[y]) x = fa[x][i];
    }
    if(x == y) return x;
    for(int i = maxi; i >= 0; i--){
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[y][0];
}
int get_dis(int u, int v){
    int lca = get_lca(u, v);
    return dep[u] + dep[v] - 2 * dep[lca] + 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++) scanf("%d%d",&eg[i].first,&eg[i].second);
    sort(eg + 1, eg + m + 1);
    m = unique(eg + 1, eg + m + 1) - eg - 1;
    for(int i = 1; i <= m; i++){
        int u = eg[i].first, v = eg[i].second;
        add_edge(u, v); add_edge(v, u);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]){
            root = i;
            tarjan(i, 0);
        }
    }
    for(int now = 1; now <= n; now++){
        for(int i = head[now]; i; i = e[i].pre){
            if(col[now] != col[e[i].to]){
                g[col[now]].push_back(col[e[i].to]);
                g[col[e[i].to]].push_back(col[now]);
            }
        }
    }
    bfs(col[1]);
    for(int i = 1; (1 << i) < n; i++){
        for(int j = 1; j <= n; j++){
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
        }
    }
    int q; scanf("%d",&q);
    while(q--){
        int u, v;
        scanf("%d%d",&u,&v);
        int res = get_dis(col[u], col[v]);
        vector<int> ans;
        while(res){
            ans.push_back(res % 2);
            res >>= 1;
        }
        for(int i = ans.size() - 1; i >= 0; i--) printf("%d",ans[i]);
        printf("\n");
    }
    return 0;
}