圆方树的定义： 1、原图中的所有点为圆点 2、对每个点双连通分量 3、删去这个点双内部所有边 4、建立一个新的方点 5、方点向所有点双中的点连边

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int> G1[N], G2[N<<1];
int n, m, tsp, cnt, dfn[N], low[N];
stack<int> stk;

void tarjan(int x) {
    dfn[x] = low[x] = ++tsp;
    stk.push(x);
    for(int y : G1[x]) {
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if(dfn[x] == low[y]) {
                cnt++;
                G2[x].push_back(cnt);
                for(int z = -1; z != y;) {
                    z = stk.top(); stk.pop();
                    G2[cnt].push_back(z);
                }
            }
        } else {
            low[x] = min(low[x], dfn[y]);
        }
    }
}

int D, dep[N<<1], d[N<<1], st[N<<1][20];

void dfs(int x, int xfa) {
    dep[x] = dep[xfa] + 1;
    d[x] = d[xfa] + (x <= n);
    st[x][0] = xfa;
    for(int i = 1; i <= D; i++) st[x][i] = st[st[x][i-1]][i-1];
    for(int y : G2[x]) if(y != xfa) dfs(y, x);
}

int LCA(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = D; i >= 0; i--) if(dep[st[x][i]] >= dep[y]) x = st[x][i];
    if(x == y) return y;
    for(int i = D; i >= 0; i--) if(st[x][i] != st[y][i]) x = st[x][i], y = st[y][i];
    return st[x][0];
}

int dist(int x, int y) {
    int lca = LCA(x, y);
    int ans = d[x] + d[y] - 2*d[lca] + (lca <= n);
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y); if(x == y) continue;
        G1[x].push_back(y);
        G1[y].push_back(x);
    }

    tsp = 0; cnt = n; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
    for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i), stk.pop();

    D = log2(2*n); memset(dep, 0, sizeof(dep)); memset(d, 0, sizeof(d)); memset(st, 0, sizeof(st));
    for(int i = 1; i <= cnt; i++) if(dep[i] == 0) dfs(i, 0);

    int q; scanf("%d", &q);
    while(q--) {
        int i, j; scanf("%d%d", &i, &j);
        printf("%d\n", dist(i, j));
    }
    return 0;
}