WA on #1 #3 #8
MLE on #7

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int v, idx;
};

const int N = 5e4 + 5;
int n, m, tot, dfn[N], low[N], bl[N], ind, cnt;
int dep[N], anc[N][20];
bool vis[N], brg[N], vis2[N];
vector<edge> p[N];
vector<int> g[N];
stack<int> st;

void tarjan(int u, int ine) {
    low[u] = dfn[u] = ++ind;
    st.push(u);
    for (auto &[v, idx] : p[u]) {
        if (idx == ine) continue;
        if (!dfn[v]) {
            tarjan(v, idx);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                brg[idx] = true;
        } else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
}

void dfs1(int u) {
    vis2[u] = true;
    bl[u] = tot;
    for (auto &[v, idx] : p[u]) {
        if (vis2[v]) continue;
        if (brg[idx]) continue;
        dfs1(v);
    }
}

void dfs2(int u, int fa) {
    for (auto v : g[u]) {
        if (v == fa) continue;
        dep[v] = dep[u] + 1;
        anc[v][0] = u;
        dfs2(v, u);
    }
}

void init() {
    for (int k = 1; k <= 14; k++)
        for (int i = 1; i <= n; i++)
            anc[i][k] = anc[anc[i][k - 1]][k - 1];
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 14; i >= 0; i--)
        if (dep[anc[x][i]] >= dep[y]) {
            x = anc[x][i];
        }
    if (x == y) return x;
    for (int i = 14; i >= 0; i--)
        if (anc[x][i] != anc[y][i])
            x = anc[x][i], y = anc[y][i];
    return anc[x][0];
}

string to_b(int x) {
    string res;
    while (x) res += (char)(x % 2 + '0'), x /= 2;
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        p[u].push_back({v, i});
        p[v].push_back({u, i});
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);
    for (int i = 1; i <= n; i++)
    if (!vis2[i]) tot++, dfs1(i);
    
    for (int i = 1; i <= n; i++)
        for (auto &[j, idx] : p[i]) {
            int u = bl[i], v = bl[j];
            if (u != v) g[u].push_back(v);
        }

    dep[1] = 1;
    dfs2(1, 0), init();

    cin >> cnt;
    while (cnt--) {
        int x, y;
        cin >> x >> y;
        int u = bl[x], v = bl[y];
        int ac = lca(u, v);
        int ans = (dep[u] - dep[ac]) + (dep[v] - dep[ac]) + 1;
        cout << to_b(ans) << endl;
    }
    return 0;
}