裸的LCT。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline void Swap(int &a,int &b){a^=b^=a^=b;}
void read(int &x){
char c=getchar();x=;
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') x=x*+(c^),c=getchar();
}
#define N 10005
int n,m,ch[N][],fa[N],rev[N];
#define lc ch[x][0]
#define rc ch[x][1]
inline bool nrt(int x){return ch[fa[x]][]==x||ch[fa[x]][]==x;}
inline void Rev(int x){Swap(lc,rc),rev[x]^=;}
void down(int x){if(rev[x])Rev(lc),Rev(rc),rev[x]=;}
void Pre(int x){if(nrt(x))Pre(fa[x]); down(x);}
void turn(int x){
int y=fa[x],z=fa[y],l=(ch[y][]==x),r=l^;
if(nrt(y)) ch[z][ch[z][]==y]=x;
fa[ch[x][r]]=y; fa[y]=x; fa[x]=z;
ch[y][l]=ch[x][r]; ch[x][r]=y;
}
void splay(int x){
Pre(x);
for(;nrt(x);turn(x)){
int y=fa[x],z=fa[y];
if(nrt(y)) turn(((ch[z][]==y)^(ch[y][]==x))?x:y);
}
}
void access(int x){for(int y=;x;y=x,x=fa[x])splay(x),rc=y;}
inline void makert(int x){access(x),splay(x),Rev(x);}
int findrt(int x){
access(x);splay(x);down(x);
while(lc) x=lc,down(x);
splay(x); return x;
}
void link(int x,int y){makert(x); if(findrt(y)!=x) fa[x]=y;}
void cut(int x,int y){
makert(x);
if(findrt(y)==x&&fa[y]==x&&!ch[y][]) fa[y]=rc=;
}
int main(){
read(n);read(m); int q1,q2; char opt[];
while(m--){
scanf("%s",opt); read(q1); read(q2);
if(opt[]=='Q') makert(q2),puts(findrt(q1)==q2?"Yes":"No");
else if(opt[]=='C') link(q1,q2);
else if(opt[]=='D') cut(q1,q2);
}return ;
}