M.cpp

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)((x).size())
#define ll long long
#define intmax INT_MAX
#define intmin INT_MIN
#define llmax LONG_MAX
#define llmin LONG_MIN
#define pb push_back
#define f first
#define s second
#define ent '\n'

const ll infl = 1e18;
const int INF = 1e9 + 9;
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 7;

map <pair <int, int>, bool > ma;
vector <pair <int, int> > vec;

int up[MAXN][20];
int tin[MAXN], tout[MAXN], l, col[MAXN], fup[MAXN], h[MAXN];
int timer = 0;
bool was[MAXN], was2[MAXN];

vector <int> g[MAXN], g2[MAXN];
void is_bridge(int x, int y){
    ma[{x, y}] = 1;
    ma[{y, x}] = 1;
    vec.pb({x, y});
}

void dfs(int x, int pr = -1){
    was[x] = 1;
    timer++;
    tin[x] = timer;
    fup[x] = tin[x];

    for (int i = 0; i < g[x].size(); i++){
        int to = g[x][i];

        if (!was[to]){
            dfs(to, x);
            fup[x] = min(fup[x], fup[to]);
            if (tin[x] < fup[to]){
                is_bridge(x, to);
            }
        }
        else if (to != pr){
            fup[x] = min(fup[x], tin[to]);
        }

    }
}

void dfs2(int x, int color){
    was2[x] = true;
    col[x] = color;
    for (int i = 0; i < g[x].size(); i++){
        int to = g[x][i];
        if (ma.count({x, to}) == 0 && !was2[to]){
            dfs2(to, color);
        }
    }
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

void dfs3(int x, int y, int p = 0){
    was[x] = 1;
    tin[x] = ++timer;
    up[x][0] = p;
    h[x] = y;
    for (int i = 1; i <= l; i++){
        up[x][i] = up[up[x][i - 1]][i - 1];
    }

    for (int i = 0; i < g2[x].size(); i++){
        int to = g2[x][i];
        if (!was[to]){
            dfs3(to, y + 1, x);
        }
    }
    tout[x] = ++timer;
}

int lca(int a, int b){
    if (upper(a, b))
        return a;
    if (upper(b, a))
        return b;

    for (int i = l; i >= 0; i--){
        if (!upper(up[a][i], b))
            a = up[a][i];
    }

    return up[a][0];
}


void solve(){
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    dfs(1);
    int k = 0;
    for (int i = 1; i <= n; i++){
        if (!was2[i]){
            k++;
            dfs2(i, k);
        }
    }

    //cout << "!!!" << vec.size() << endl;
    for (int i = 0; i < vec.size(); i++){
        int x = vec[i].f;
        int y = vec[i].s;
        //cout << "@@@ " << col[x] << ' ' << col[y] << "\n";
        g2[col[x]].pb(col[y]);
        g2[col[y]].pb(col[x]);
    }
    for (int i = 1; i <= n; i++){
        was[i] = 0;
        tin[i] = 0;
    }
    tout[0] = INF;
    timer = 0;
    l = 0;
    while ((1 << l) < MAXN){
        l++;
    }
    dfs3(1, 0);
    int q;
    cin >> q;

    while(q--){
        int x, y;
        cin >> x >> y;
        cout << h[col[x]] + h[col[y]] - 2 * h[lca(col[x], col[y])] << "\n";
    }

}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}