RT，除了测试点#10外全都TLE了，对着题解调了一下午/px

#include<bits/stdc++.h>
#define N 500010
#define fa(x) a[x].fa
#define s(x) a[x].size
#define c(x) a[x].cnt
#define son(x,y) a[x].son[y]
#define rev(x) a[x].rev
using namespace std;
struct tree{
	int size,cnt,fa,rev,son[2];
}a[2*N];
int tot,n,m,que[N];
inline int get(int x){return son(fa(x),1)==x;}
//void update(int x){if(!x)return;s(x)=c(x);if(son(x,0))s(x)+=s(son(x,0));if(son(x,1))s(x)+=s(son(x,1));}
inline void connect(int x,int y,int z){if(x)fa(x)=y;if(y)son(y,z)=x;}
inline void pushdown(int x)
{
	if(rev(x)&&x)
	{
		if(son(x,0))rev(son(x,0))^=1;
		if(son(x,1))rev(son(x,1))^=1;
		swap(son(x,0),son(x,1));
		rev(x)=0;
	}
}
inline bool isroot(int x)
{
	if(!fa(x))return 1;
	return son(fa(x),0)!=x&&son(fa(x),1)!=x;
}
inline void rotate(int x)
{
	int f=fa(x),gf=fa(f),y=get(x),z=get(f);
	//pushdown(f);pushdown(x);
	connect(son(x,y^1),f,y);
	connect(f,x,y^1);
	fa(x)=gf;if(!isroot(f))son(gf,z)=x;
	//update(f);update(x);
}
inline void splay(int x)
{
	int top=0;que[0]=x;
	for(int i=x;!isroot(i);i=fa(i))que[++top]=fa(i);
	for(int i=top;i>=0;i--)pushdown(que[i]);
	for(int f=fa(x);!isroot(x);rotate(x),f=fa(x))
		if(!isroot(f))
			rotate((get(x)==get(f))?f:x);
}
inline void access(int x)
{
	for(int y=0;x;y=x,x=fa(x))
	{
		splay(x);son(x,1)=y;
		//update(x);
		if(y)fa(y)=x;
	}
}
int findroot(int x)
{
	access(x);splay(x);
	while(pushdown(x),son(x,0))x=son(x,0);
	splay(x);return x;
}
inline void makeroot(int x)
{
	access(x);splay(x);
	rev(x)^=1;return;
}
inline void select(int x,int y)
{makeroot(x);access(y);splay(y);}
inline void link(int x,int y)
{
	makeroot(x);
	/*if(findroot(y)!=x)*/fa(x)=y;
}
inline void cut(int x,int y)
{
	select(x,y);
	//if(son(y,0)!=x||son(x,1))return;
	son(y,0)=0;fa(x)=0;
}
int main()
{
	ios::sync_with_stdio(0);
	int x,y;
	string opt;
	cin>>n>>m;
	//for(int i=1;i<=n;i++)c(i)=s(i)=1;
	while(m--)
	{
		cin>>opt>>x>>y;
		if(opt[0]=='Q')
		{
			if(findroot(x)==findroot(y))cout<<"Yes\n";
			else cout<<"No\n";
		}
		else if(opt[0]=='C')link(x,y);
		else cut(x,y);
	}
}