trick+树剖
首先删边操作困难，考虑倒序处理。
发现题目中的关键性质：无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。
这说明无论何时图都是连通的，那么我们完全可以建一棵树，再考虑加边对树的影响。
首先如果是树，那么两点路径唯一，关键航线数量即为路径长度。若此时加了一条边，一定会在树上形成一个环，此时环上任意一条边再断开对图的连通性不会有任何影响，那么环上的边不可能为关键航线了。
这个操作其实就是路径覆盖 \(0\)，树剖维护即可。
建树的操作我是用并查集维护的。
复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 30010, M = 1e6;
int n, m, k, cnt, q;
int fa[N], vis[M], h[N], ans[M];
std::map<pii, int> mp;
std::vector<pii> E;
std::vector<std::array<int, 3>> G;
int find(int x) {
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
struct node {
int to, nxt;
} e[N << 1];
void add(int u, int v) {
e[++cnt].to = v, e[cnt].nxt = h[u], h[u] = cnt;
}
int num;
int sz[N], dep[N], id[N], son[N], anc[N], top[N];
void dfs1(int u, int fa) {
sz[u] = 1;
dep[u] = dep[fa] + 1;
anc[u] = fa;
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs1(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int topf) {
top[u] = topf;
id[u] = ++num;
if(!son[u]) return;
dfs2(son[u], topf);
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == anc[u] || v == son[u]) continue;
dfs2(v, v);
}
}
struct seg {
int v, lzy;
} t[N << 2];
void pushup(int u) {t[u].v = t[u << 1].v + t[u << 1 | 1].v;}
void pd(int u) {
if(!t[u].lzy) return;
t[u << 1].v = t[u << 1 | 1].v = 0;
t[u << 1].lzy = t[u << 1 | 1].lzy = 1;
t[u].lzy = 0;
}
void build(int u, int l, int r) {
if(l == r) {
if(l != 1) t[u].v = 1;
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void update(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) {
t[u].v = 0, t[u].lzy = 1;
return;
}
int mid = (l + r) >> 1; pd(u);
if(L <= mid) update(u << 1, l, mid, L, R);
if(R > mid) update(u << 1 | 1, mid + 1, r, L, R);
pushup(u);
}
int query(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) return t[u].v;
int mid = (l + r) >> 1, ret = 0; pd(u);
if(L <= mid) ret += query(u << 1, l, mid, L, R);
if(R > mid) ret += query(u << 1 | 1, mid + 1, r, L, R);
return ret;
}
int qry(int u, int v) {
int ret = 0;
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
ret += query(1, 1, n, id[top[u]], id[u]);
u = anc[top[u]];
}
if(dep[u] > dep[v]) std::swap(u, v);
ret += query(1, 1, n, id[u] + 1, id[v]);
return ret;
}
void mdf(int u, int v) {
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
update(1, 1, n, id[top[u]], id[u]);
u = anc[top[u]];
}
if(dep[u] > dep[v]) std::swap(u, v);
update(1, 1, n, id[u] + 1, id[v]);
}
void Solve() {
std::cin >> n >> m;
E.pb({0, 0}), G.pb({0, 0});
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= m; i++) {
int u, v;
std::cin >> u >> v;
E.pb({u, v});
mp[{u, v}] = i;
}
while(1) {
int op;
std::cin >> op;
if(op == -1) break;
int u, v;
std::cin >> u >> v;
if(op == 1) G.pb({++q, u, v});
else {
G.pb({0, u, v});
E[mp[{u, v}]] = {0, 0};
}
k++;
}
for(auto x : E) {
if(x.fi) G.pb({0, x.fi, x.se});
}
std::reverse(G.begin() + 1, G.end());
int g = G.size();
for(int i = 1; i <= g - k - 1; i++) {
int x = find(G[i][1]), y = find(G[i][2]);
if(x == y) continue;
vis[i] = 1, fa[x] = y;
add(G[i][1], G[i][2]), add(G[i][2], G[i][1]);
}
dfs1(1, 0), dfs2(1, 1), build(1, 1, n);
for(int i = 1; i < g; i++) {
if(vis[i]) continue;
if(G[i][0]) {
ans[G[i][0]] = qry(G[i][1], G[i][2]);
} else {
mdf(G[i][1], G[i][2]);
}
}
for(int i = 1; i <= q; i++) std::cout << ans[i] << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}