分析

考虑求出边双连通分量，那么题目其实就是在问，有多少个桥。那么由于边双缩点之后，整个图变为树。那么树的边数就是答案。考虑新加一条边之后的贡献。那么就是树上距离，在将这个链上的权值变为 。这个考虑树链剖分或者 维护，写完才发现，好像直接并查集时间复杂度好像还要更优。这里采用了 实现，时间总复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 4e5 + 1000;
struct Lct {
    bool r[N];
    int val[N],sum[N],ch[N][2],tag[N],fa[N];
    void pushr(int x) {swap(ch[x][1],ch[x][0]);r[x] ^= 1;}
    bool nroot(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
    void pushup(int x) {sum[x] = (val[x] + sum[ch[x][0]] + sum[ch[x][1]]);}
    void pusha(int x) {sum[x] = val[x] = 0;tag[x] = 1;}
    void pushdown(int x) {
        if(r[x]) {if(ch[x][0]) pushr(ch[x][0]);if(ch[x][1]) pushr(ch[x][1]);r[x] = 0;}
        if(tag[x]) {if(ch[x][0]) pusha(ch[x][0]);if(ch[x][1]) pusha(ch[x][1]);tag[x] = 0;}
    }
    void push(int x) {if(nroot(x))push(fa[x]);pushdown(x);}
    void rotate(int x) {
        int y = fa[x],z = fa[y],k = (ch[y][1] == x),w = ch[x][!k];
        if(nroot(y)) ch[z][ch[z][1] == y] = x;ch[y][k] = w;ch[x][!k] = y;
        if(w) fa[w] = y;fa[x] = z;fa[y] = x;pushup(y);
    }
    void splay(int x) {
        push(x);while(nroot(x)) {
            int y = fa[x],z = fa[y];
            if(nroot(y)) rotate(((ch[z][1]==y)^(ch[y][1]==x))?y:x);
            rotate(x);pushup(x);
        }
    }
    void access(int x) {for(int y = 0;x;x = fa[y=x])splay(x),ch[x][1]=y,pushup(x);}
    void makeroot(int x) {access(x);splay(x);pushr(x);}
    void split(int x,int y) {makeroot(x);access(y);splay(y);}
    void link(int x,int y) {split(x,y);fa[x] = y;}
    int ask(int x,int y) {split(x,y);int ans = sum[y];pusha(y);return ans;}
    void clear(int tot) {for(int x=0;x<=tot;x++)ch[x][1]=ch[x][0]=tag[x]=val[x]=sum[x]=r[x]=fa[x]=0;}
}t;
int low[N],dfn[N],dcc[N],vis[N],st[N],top,n,m,tot,Dfn,Dcc;
vector<int> G[N],id[N];
void tarjan(int x,int fa) {
    low[x] = dfn[x] = ++Dfn;
    st[++top] = x;vis[x] = 1;
    for(int i = 0 ;i < G[x].size();i++) {
        if(id[x][i] == fa) continue;int y = G[x][i];
        if(!dfn[y]) tarjan(y,id[x][i]),low[x] = min(low[x],low[y]);
        else if(vis[y]) low[x] = min(dfn[y],low[x]);
    }
    if(low[x] == dfn[x]) {
        Dcc++;dcc[x] = Dcc;vis[x] = 0;
        while(st[top] != x) {
            dcc[st[top]] = Dcc;vis[st[top]] = 0;
            top--;
        }
        top--;
    }
}
int main() {
    int Case = 0;
    while(1) {
        n = read();m = read();
        if(n == 0 && m == 0) break;printf("Case %d:\n",++Case);
        t.clear(tot);tot = 0;Dfn = 0,Dcc = 0;top = 0;
        for(int i = 1;i <= n;i++) {
            G[i].clear();id[i].clear();
            st[i] = vis[i] = low[i] = dfn[i] = dcc[i] = 0;
        }
        for(int i = 1;i <= m;i++) {
            int u = read(),v = read();
            G[u].push_back(v);G[v].push_back(u);
            id[u].push_back(i);id[v].push_back(i);
        }
        for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i,0);
        tot = Dcc;
        for(int x = 1;x <= n;x++) {
            for(auto y : G[x]) {
                if(x > y) continue;
                if(dcc[y] == dcc[x]) continue;
                ++tot;t.val[tot] = 1;
                t.link(dcc[y],tot);
                t.link(dcc[x],tot);
            }
        }
        int Q = read(),res = 0;
        while(Q--) {
            int x = read(),y = read();
            if(dcc[x] != dcc[y]) res += t.ask(dcc[x],dcc[y]);
            printf("%d\n",Dcc - res - 1);
        }
        printf("\n");
    }
}