分析

首先我们先求出整张图最开始的边双连通分量
然后考虑之后加边操作对答案的贡献
我们发现，当加入一条从双连通块x到y的边后
树上（边双连通分量构成的树）从x到y路径上的所有边都不再对答案有贡献了
所以我们主要的任务就是如何剪掉这部分的贡献

本题提供3种做法：

算法一

由于数据范围所以我们直接暴力跳即可
时间复杂度：

算法二

由于我们支持的是一条链的修改，自然想到树链剖分
在dfn线段树上支持区间赋值，区间求和即可
时间复杂度：

算法三

（是JK_LOVER大佬的维护方式）
即直接用lct进行修改链上信息
时间复杂度：

代码

由于本人比较懒，只写了不动脑子的算法一

//Nowcoder 51266
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define ll long long
#define cl(x, y) memset((x), (y), sizeof(x))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define de(x) cerr << #x << " = " << x << " "
#define inc_mod(x, y) x = ((x - y) % mod + mod) % mod
#define add_mod(x, y) x = (x + y) % mod
#define mul_mod(x, y) x = (x * y) % mod
#define lowbit(x) (x & (-x))
#define inf 0x3f3f3f3f
#define mod 998244353
#define rson (x << 1 | 1)
#define lson (x << 1)
using namespace std;
const int maxn = 1e5 + 10;

int total, side, test, u, v, w, opt, ans, cas;
int nxt[maxn << 2], ed[maxn << 2], head[maxn], cur;
int col[maxn], gro[maxn], fa[maxn];
int dfn[maxn], low[maxn], dfn_num;

inline void file() {
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}

inline int find_fa(int now) {
    if(gro[now] == now) return now;
    else return gro[now] = find_fa(gro[now]);
}

inline void tarjan(int now, int pre) {
    fa[now] = pre;
    dfn[now] = low[now] = ++dfn_num;
    for(int i = head[now]; i; i = nxt[i]) {
        if(ed[i] == pre) continue;
        if(!dfn[ed[i]]) {
            tarjan(ed[i], now);
            low[now] = min(low[now], low[ed[i]]);
            if(low[ed[i]] > dfn[now]) ans++;
            else gro[find_fa(ed[i])] = find_fa(now);
        } else low[now] = min(low[now], dfn[ed[i]]);
    }
}

inline void add_edge(int from, int to) {
    nxt[++cur] = head[from];
    head[from] = cur;
    ed[cur] = to;
}

inline void solve(int x, int y) {
    if(dfn[x] < dfn[y]) swap(x, y);
    while(dfn[x] > dfn[y]) {
        int a = find_fa(x), b = find_fa(fa[x]);
        if(a != b) ans--, gro[a] = b;
        x = fa[x];
    }
    while(x != y) {
        int a = find_fa(y), b = find_fa(fa[y]);
        if(a != b) ans--, gro[a] = b;
        y = fa[y];
    }
}

int main() {
    // file();
    ios::sync_with_stdio(false);
    while(cin >> total >> side) {
        if(total == 0 && side == 0) break;
        cl(head, 0); 
        cur = 0; dfn_num = 0; ans = 0;
        cl(low, 0); cl(dfn, 0);
        rep(i, 1, total) gro[i] = i;
        rep(i, 1, side) {
            cin >> u >> v;
            add_edge(u, v);
            add_edge(v, u);
        }
        tarjan(1, 0);
        cin >> test;
        cout << "Case " << ++cas << ":" << endl;
        while(test--) {
            cin >> u >> v;
            solve(u, v);
            cout << ans << endl;
        }
        cout << endl;
    }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}