#include<bits/stdc++.h>
#define ls s[0]
#define rs s[1]
#define setson(u,c,v) t[u].s[c] = (u ? v : 0), t[v].p = u
#define get(x) (t[x].p[t].rs == x)
#define isrt(x) (t[x].p[t].ls != x && t[x].p[t].rs != x) 
using namespace std;
const int maxn = 1e5+10;
struct { int p,s[2],tag; }t[maxn];
int a,b,n,m;char opt[8];
void revs(int u) { t[u].tag ^= 1, swap(t[u].ls,t[u].rs); }
void pushup(int) {}
void pushdown(int u) { if(t[u].tag) revs(t[u].ls),revs(t[u].rs),t[u].tag=0; }
void rota(int x) {
	int y = t[x].p, z = t[y].p, c = get(x);
	if(!isrt(y)) t[z].s[get(y)] = x;
	setson(y,c,t[x].s[!c]);
	setson(x,!c,y),t[x].p = z;
	pushup(y),pushup(x);
}
void upd(int u) {
	if(!isrt(u)) upd(t[u].p);
	pushdown(u);
}
void splay(int u) {
	upd(u);
	for(int p;p = t[u].p, !isrt(u);rota(u))
		if(!isrt(p)) rota(get(u)^get(p)?u:p);
}
int acc(int u,int p=0) {
	for(;u;u = t[p=u].p) splay(u),t[u].rs = p,pushup(u);
	return p;
}
void mkrt(int u) { revs(acc(u)); }
void split(int u,int p) { mkrt(u),acc(p),splay(p); }
void link(int u,int p) { mkrt(u), t[u].p = p; }
void cut(int u,int p) { split(u,p),t[p].ls = t[u].p = 0,pushup(p); }
int find(int u) {
	acc(u),splay(u);
	while(t[u].ls) pushdown(u=t[u].ls);
	return u;
}
signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	while(m--) {
		cin>>opt>>a>>b;
		if(opt[0] == 'Q') cout<<(find(a)==find(b) ? "Yes\n":"No\n");
		if(opt[0] == 'C') link(a,b);
		if(opt[0] == 'D') cut(a,b);
	}
}

只通过了 subtask12，求助