题面

Sol

把询问反过来，变成加边，先加上边变成一棵树，之后每次加边就相当于去掉这两个点与这条边形成的环的代价，用树剖+线段树覆盖区间即可

# include 
    
     # define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(3e5 + 10);IL ll Read(){    RG ll x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}int n, fst[_], nxt[_], to[_], cnt, m, Q, ans[_], use[_];int dfn[_], Index, fa[_], size[_], top[_], son[_], deep[_];int sum[_ << 1], cov[_ << 1];struct Qry{    int c, u, v, id;    IL bool operator <(RG Qry A) const{        if(c != A.c) return c < A.c;        return u != A.u ? u < A.u : v < A.v;    }} qry[_];struct Edge{    int u, v, flg;    IL bool operator <(RG Edge A) const{  return u != A.u ? u < A.u : v < A.v;  }} edge[_];IL void Add(RG int u, RG int v){  to[cnt] = v; nxt[cnt] = fst[u]; fst[u] = cnt++;  }IL int Find(RG int x){  return x == fa[x] ? x : fa[x] = Find(fa[x]);  }IL void Dfs1(RG int u, RG int ff){    size[u] = 1; fa[u] = ff; deep[u] = deep[ff] + 1;    for(RG int e = fst[u]; e != -1; e = nxt[e]){        if(to[e] == ff) continue;        Dfs1(to[e], u);        size[u] += size[to[e]];        if(size[to[e]] > size[son[u]]) son[u] = to[e];    }}IL void Dfs2(RG int u, RG int Top){    top[u] = Top; dfn[u] = ++Index;    if(son[u]) Dfs2(son[u], Top);    for(RG int e = fst[u]; e != -1; e = nxt[e]) if(!dfn[to[e]]) Dfs2(to[e], to[e]);}IL void Build(RG int x, RG int l, RG int r){    sum[x] = r - l + 1;    if(l == r) return;    RG int mid = (l + r) >> 1;    Build(x << 1, l, mid); Build(x << 1 | 1, mid + 1, r);}IL void Pushdown(RG int x){    if(!cov[x]) return;    cov[x << 1] = cov[x << 1 | 1] = 1;    cov[x] = sum[x << 1] = sum[x << 1 | 1] = 0;}IL void Modify(RG int x, RG int l, RG int r, RG int L, RG int R){    if(L <= l && R >= r){  sum[x] = 0; cov[x] = 1; return;  }    RG int mid = (l + r) >> 1;    Pushdown(x);    if(L <= mid) Modify(x << 1, l, mid, L, R);    if(R > mid) Modify(x << 1 | 1, mid + 1, r, L, R);    sum[x] = sum[x << 1] + sum[x << 1 | 1];}IL int Query(RG int x, RG int l, RG int r, RG int L, RG int R){    if(L <= l && R >= r) return sum[x];    RG int mid = (l + r) >> 1, ans = 0;    Pushdown(x);    if(L <= mid) ans = Query(x << 1, l, mid, L, R);    if(R > mid) ans += Query(x << 1 | 1, mid + 1, r, L, R);    sum[x] = sum[x << 1] + sum[x << 1 | 1];    return ans;}IL void Cover(RG int u, RG int v){    while(top[u] ^ top[v]){        if(deep[top[u]] < deep[top[v]]) swap(u, v);        Modify(1, 1, n, dfn[top[u]], dfn[u]);        u = fa[top[u]];    }    if(deep[u] > deep[v]) swap(u, v);    if(u != v) Modify(1, 1, n, dfn[u] + 1, dfn[v]);}IL int Calc(RG int u, RG int v){    RG int ret = 0;    while(top[u] ^ top[v]){        if(deep[top[u]] < deep[top[v]]) swap(u, v);        ret += Query(1, 1, n, dfn[top[u]], dfn[u]);        u = fa[top[u]];    }    if(deep[u] > deep[v]) swap(u, v);    if(u != v) ret += Query(1, 1, n, dfn[u] + 1, dfn[v]);    return ret;}IL bool Cmp(RG Qry A, RG Qry B){  return A.id > B.id;  }int main(RG int argc, RG char* argv[]){    n = Read(); m = Read();    for(RG int i = 1; i <= n; ++i) fa[i] = i, fst[i] = -1;    for(RG int i = 1; i <= m; ++i){        edge[i].u = Read(), edge[i].v = Read();        if(edge[i].u > edge[i].v) swap(edge[i].u, edge[i].v);    }    for(RG int c = Read(); c != -1; c = Read()){        ans[++Q] = -1; qry[Q].u = Read(); qry[Q].v = Read(); qry[Q].c = c; qry[Q].id = Q;        if(qry[Q].u > qry[Q].v) swap(qry[Q].u, qry[Q].v);    }    sort(edge + 1, edge + m + 1); sort(qry + 1, qry + Q + 1);    RG int g = Q;    for(RG int i = 1; i <= Q; ++i) if(qry[i].c){  g = i; break;  }    for(RG int l = 1, r = 1; l <= m && r <= g; ++l){        while((qry[r].u < edge[l].u || (qry[r].u == edge[l].u && qry[r].v < edge[l].v)) && r <= g) ++r;        if(qry[r].u == edge[l].u && qry[r].v == edge[l].v) edge[l].flg = 1;    }    sort(qry + 1, qry + Q + 1, Cmp);    for(RG int i = 1; i <= m; ++i){        if(edge[i].flg) continue;        RG int fx = Find(edge[i].u), fy = Find(edge[i].v);        if(fx == fy) continue;        fa[fx] = fy; use[i] = 1;        Add(edge[i].u, edge[i].v); Add(edge[i].v, edge[i].u);    }    Dfs1(1, 0); Dfs2(1, 1); Build(1, 1, n);    for(RG int i = 1; i <= m; ++i) if(!edge[i].flg && !use[i]) Cover(edge[i].u, edge[i].v);    for(RG int i = 1; i <= Q; ++i)        if(qry[i].c == 0) Cover(qry[i].u, qry[i].v);        else ans[qry[i].id] = Calc(qry[i].u, qry[i].v);    for(RG int i = 1; i <= Q; ++i) if(ans[i] != -1) printf("%d\n", ans[i]);    return 0;}