圆方树95ptsTLE求改

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10;
vector<int> g[N], ng[N];
int dfn[N], low[N], T, stk[N], top, cnt;
int f[N][21], dep[N];
int n, m, q;
void tarjan(int u, int fr) {
    dfn[u] = low[u] = ++T;
    stk[++top] = u;
    for(int v : g[u]) {
        if(v == fr) continue; 
        if(dfn[v] == 0) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                ++cnt;
                int x;
                do {
                    x = stk[top--];
                    ng[x].push_back(cnt);
                    ng[cnt].push_back(x);
                } while(x != v);
                ng[u].push_back(cnt);
                ng[cnt].push_back(u);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}
void dfs(int u, int fr) {
    dep[u] = dep[fr] + 1;
    f[u][0] = fr;
    for(int i = 1; i <= 20; i++) 
        f[u][i] = f[f[u][i-1]][i-1]; 
    
    for(int v : ng[u]) 
        if(v != fr) 
            dfs(v, u);
}

int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int j = 20; j >= 0; j--)
        if(dep[f[u][j]] >= dep[v])
            u = f[u][j];
    if(u == v) return u;
    for(int j = 20; j >= 0; j--)
        if(f[u][j] != f[v][j])
            u = f[u][j], v = f[v][j];
    return f[u][0];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int u, v;
    for(int i = 1; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }  
    cnt = n; 
    tarjan(1, 0);
    dfs(1, 0);
    cin >> q;
    while(q--) {
        cin >> u >> v;
        int l = lca(u, v); 
        int ans = (dep[u] + dep[v] - 2 * dep[l] + 2) / 2;
        cout << ans << endl;
    }
    return 0;
}