解法
Easy
削除のみの場合． クエリを先読みして，逆に処理すれば，union-find で解ける．
Normal
追加と削除の場合． ただし，追加する辺が 10個以下．
この場合もベースになるのは Easy版で，クエリ先読みと逆順処理をする． もとのクエリで追加する辺(逆順処理では削除する辺)は少ないので， その度に union-find を構成しなおしても間に合う．
実装
Union-find を再構成するために， 逆順で処理したときに，追加した辺を記録しておく．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
UnionFind<ll> uf;
set<pll> es;
rep(i,m){
ll a,b; cin >> a >> b;
--a, --b;
es.insert({a,b});
}
ll q; cin >> q;
vector<tuple<ll,ll,ll>> qs;
rep(qi,q){
ll t,x,y; cin >> t >> x >> y;
--x,--y;
qs.emplace_back(t,x,y);
if(t == 1){
es.insert({x,y});
}else if(t == 2){
assert(es.find({x,y}) != es.end());
es.erase({x,y});
}
}
reverse(all(qs));
auto create_uf = [&](void) -> UnionFind<ll> {
UnionFind<ll> ret(n);
for(auto [a,b]: es){
ret.merge(a,b);
}
return ret;
};
uf = create_uf();
vector<string> ans;
for(auto [t,x,y]: qs){
if(t == 1){
es.erase({x,y});
uf = create_uf();
}else if(t == 2){
es.insert({x,y});
uf.merge(x,y);
}else{
ans.push_back(uf.same(x,y) ? "Yes" : "No");
}
}
reverse(all(ans)); // rem: reverse
for(auto s: ans){
cout << s << endl;
}
return 0;
}
