思路：

按时间分治，然后每条边有一个存活时间段，按存活时间段将边加入划分树，然后在划分树上分治，用可撤销并查集维护连通性。

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
     
      #define pli pair
      
       #define pii pair
       
        #define piii pair
        
         #define pdd pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 1e4 + 10, M = 2e5 + 5;vector
          
            vc[M<<2];int n, m, u[M], v[M], op[M];struct UFS { stack
           
            
             > stk; int fa[N], rnk[N]; inline void init(int n) { for (int i = 0; i <= n; ++i) fa[i] = i, rnk[i] = 0; } inline int Find(int x) { while(x^fa[x]) x = fa[x]; return x; } inline void Merge(int x, int y) { x = Find(x), y = Find(y); if(x == y) return ; if(rnk[x] <= rnk[y]) { stk.push({fa+x, fa[x]}); fa[x] = y; if(rnk[x] == rnk[y]) { stk.push({rnk+y, rnk[y]}); rnk[y]++; } } else { stk.push({fa+y, fa[y]}); fa[y] = x; } } inline void Undo() { *stk.top().fi = stk.top().se; stk.pop(); }}ufs;void update(int L, int R, pii p, int rt, int l, int r) { if(L <= l && r <= R) return vc[rt].pb(p), void(); int m = l+r >> 1; if(L <= m) update(L, R, p, ls); if(R > m) update(L, R, p, rs);}void dfs(int rt, int l, int r) { for (pii p : vc[rt]) ufs.Merge(p.fi, p.se); if(l == r){ if(op[l] == 2) { if(ufs.Find(u[l]) == ufs.Find(v[l])) printf("Yes\n"); else printf("No\n"); } return ; } int m = l+r >> 1; int sz = ufs.stk.size(); dfs(ls); while(ufs.stk.size() > sz) ufs.Undo(); dfs(rs); while(ufs.stk.size() > sz) ufs.Undo();}char s[15];map
             
               mp;int main() { scanf("%d %d", &n, &m); ufs.init(n); for (int i = 1; i <= m; ++i) { scanf("%s", s); scanf("%d %d", &u[i], &v[i]); if(u[i] > v[i]) swap(u[i], v[i]); if(s[0] == 'C') op[i] = 0; else if(s[0] == 'D') op[i] = 1; else op[i] = 2; if(!op[i]) mp[{u[i], v[i]}] = i; else if(op[i] == 1) { update(mp[{u[i], v[i]}], i-1, {u[i], v[i]}, 1, 1, m); mp[{u[i], v[i]}] = 0; } } for (auto it : mp) if(it.se) update(it.se, m, it.fi, 1, 1, m); dfs(1, 1, m); return 0;}