Description:

@card{

给定一个无向图，多次询问一条边到另一条边的必经点，要求$O(n + m\log{n})$

}

Solution:

@card{

做法十分显然，点双联通分量缩点后跑lca即可，问题在于一些细节的处理。

涉及到点双联通分量的题，绝对不要在tarjan的过程建新图，由于存在根节点与孤立点的特判，在tarjan未结束前建图十分危险，非常容易写错，不如直接用vector都存下来，虽然代码长一些，常数大一些，但是不容易写错。

点双建新图的过程是对每个被判定为割点的点，给一个新编号，并向所有包含它的点双连边，最终会缩成一棵树。考虑本题的询问，虽然一个割点可能在多个点双联通分量里，但是一条边必然只在一个点双里，我们找出每条边在哪个点双里即可。

注意这里边属于哪个分量不能乱搞，尽量老老实实对每个强联通分量考虑，当且仅当一条边连的两个点都属于同一个强联通分量时，这条边才属于这个强联通分量，由于存在割点，不能随意判断，是存在”连接两个割点”的边的。

然后在新图上求出这两个点双的lca，问题即转化成这两个点的路径上有几个我们新建的割点。可以发现，缩点后的新图两个分量中间必然有一个新建割点。即我们随便提一个分量当根，偶数层必然是割点，奇数层必然是分量。不妨把这条路径拆成$x$到$lca$和$y$到$lca$，问题即转换成$[deep_{lca}, deep_{x}]$之间有几个偶数，显然可以直接算出。这里还需要注意一个细节，$lca$不能被计算两次。

求lca我采用了树剖，常数较小。

}

Code:

@card{

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

#define rint register int
#define lint long long
#define isnum(x) ('0' <= (x) && (x) <= '9')
template<typename tint>
inline void readint(tint& x) {
    int f = 1; char ch = getchar(); x = 0;
    for(; !isnum(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isnum(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= f;
}
using namespace std;
const int maxn = 20000 + 10; // 割点双倍
const int maxm = 2e5 + 10;

namespace G2{
    int head[maxn], ev[maxm], nxt[maxm], totedge = 1;
    inline void addedge(int nu, int nv) {
        ev[++totedge] = nv, nxt[totedge] = head[nu], head[nu] = totedge;
    }

    // 偶数层是割点
    int dfa[maxn], deep[maxn], size[maxn];
    int wtop[maxn], wson[maxn];
    void clear(int n) {
        int msize = sizeof(int) * (n + 1);
        memset(dfa, 0, msize), memset(deep, 0, msize), memset(size, 0, msize);
        memset(wtop, 0, msize), memset(wson, 0, msize);
        memset(head, 0, msize), totedge = 1;
    }

    void dfs1(int x, int d, int fa) {
        dfa[x] = fa, deep[x] = d, size[x] = 1;
        for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
            if(y == fa) continue;
            dfs1(y, d + 1, x);
            size[x] += size[y];
            if(size[y] > size[wson[x]]) wson[x] = y;
        }
    }
    void dfs2(int x, int top) {
        wtop[x] = top;
        if(wson[x]) dfs2(wson[x], top);
        for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
            if(y == dfa[x] || y == wson[x]) continue;
            dfs2(y, y);
        }
    }
    int lca(int x, int y) {
        while(wtop[x] != wtop[y]) {
            if(deep[wtop[x]] < deep[wtop[y]]) swap(x, y);
            x = dfa[wtop[x]];
        }
        return deep[x] < deep[y] ? x : y;
    }
    void init() { dfs1(1, 1, 0), dfs2(1, 1); }
    int ask(int x, int y) {
        int nlca = lca(x, y);
        return deep[x] / 2 - deep[nlca] / 2 + deep[y] / 2 - (deep[nlca] - 1) / 2;
    }

};

namespace G1{
    int n, m;
    int head[maxn], ev[maxm], nxt[maxm], totedge = 1;
    inline void addedge(int nu, int nv) {
        ev[++totedge] = nv, nxt[totedge] = head[nu], head[nu] = totedge;
    }

    int cut[maxn];
    int now_id[maxn];
    int dcc_id[maxn], edge_dcc_id[maxm], totdcc = 0;
    int dfn[maxn], low[maxn], totdfn = 0;
    int s[maxn], stop = 0;
    vector<int> dcc[maxn];
    void clear() {
        G2::clear(totdcc);
        int msize = sizeof(int) * (n + 1);
        memset(head, 0, msize), totedge = 1;
        memset(cut, 0, msize), memset(dcc_id, 0, msize), memset(edge_dcc_id, 0, msize);
        memset(dfn, 0, msize), memset(low, 0, msize);
        for(rint i=1; i<=totdcc; i++) dcc[i].clear();
        stop = totdfn = totdcc = 0;
    }

    void dfs(int x, int fa) {
        dfn[x] = low[x] = ++totdfn, s[++stop] = x;
        for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
            if(dfn[y] == 0) dfs(y, x), low[x] = min(low[x], low[y]);
            else low[x] = min(low[x], dfn[y]);
        }
        if(fa && low[x] >= dfn[fa]) {
            ++totdcc, cut[fa]++;
            do dcc_id[s[stop]] = totdcc, dcc[totdcc].push_back(s[stop]);
            while(s[stop--] != x);
            dcc[totdcc].push_back(fa);
        }
        if(fa == 0) cut[x] = cut[x] >= 2 ? cut[x] : 0;
    }

    void work() {
        while(cin >> n >> m && (n || m)) {
            int nu, nv;
            while(m--) {
                readint(nu), readint(nv);
                addedge(nu, nv), addedge(nv, nu);
            }
            for(rint x=1; x<=n; x++) if(dfn[x] == 0) dfs(x, 0);
            for(rint x=1; x<=n; x++) if(cut[x]) dcc_id[x] = ++totdcc;
            for(rint t=1; t<=totdcc; t++) {
                for(rint p=0; p<dcc[t].size(); p++) now_id[dcc[t][p]] = t; // 割点不能乱high
                for(rint p=0; p<dcc[t].size(); p++) {
                    int x = dcc[t][p];
                    for(rint i=head[x], y=ev[i]; i; i=nxt[i], y=ev[i]) {
                        if(now_id[y] == t) edge_dcc_id[i / 2] = t;
                    }
                    if(cut[x]) G2::addedge(dcc_id[x], t), G2::addedge(t, dcc_id[x]);
                }
            }
            G2::init();
            readint(m);
            while(m--) {
                readint(nu), readint(nv);
                printf("%d\n", G2::ask(edge_dcc_id[nu], edge_dcc_id[nv]));
            }
            clear();
        }
    }
}; 

int main() {
    G1::work();
    return 0;
}

}