1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
return data*w;
}
const int maxn(1e4+10);
int n, m;
int fa[maxn], son[2][maxn], stk[maxn], top;
bool rev[maxn];
inline bool isroot(int x) { return son[0][fa[x]]!=x&&son[1][fa[x]]!=x; }
inline bool get_son(int x) { return son[1][fa[x]]==x; }
inline void pushdown(int x)
{
if(rev[x])
{
rev[son[0][x]]^=1;
rev[son[1][x]]^=1;
rev[x]=0;
swap(son[0][x], son[1][x]);
}
}
inline void rotate(int x)
{
int f=fa[x], g=fa[f], l=get_son(x), r=l^1;
if(!isroot(f)) son[get_son(f)][g]=x;
fa[x]=g; fa[f]=x; fa[son[r][x]]=f;
son[l][f]=son[r][x]; son[r][x]=f;
}
inline void splay(int x)
{
top=1; stk[top]=x;
for(RG int i=x;!isroot(i);i=fa[i]) stk[++top]=fa[i];
for(RG int i=top;i;i--) pushdown(stk[i]);
for(;!isroot(x);rotate(x)) if(!isroot(fa[x])) rotate(get_son(fa[x])^get_son(x)?x:fa[x]);
}
inline void access(int x) { for(RG int t=0;x;t=x, x=fa[x]) splay(x), son[1][x]=t; }
inline void makeroot(int x) { access(x); splay(x); rev[x]^=1; }
inline void split(int x, int y) { makeroot(x); access(y); splay(y); }
inline void link(int x, int y) { makeroot(x); fa[x]=y; }
inline void cut(int x, int y) { split(x, y); if(son[0][y]==x) son[0][y]=0; fa[x]=0; }
inline int find(int x) { access(x); splay(x); while(son[0][x]) x=son[0][x]; return x; }
char s[10];
int a, b;
int main()
{
n=read(); m=read();
while(m--)
{
scanf("%s", s); a=read(); b=read();
if(s[0]=='C') link(a, b);
else if(s[0]=='D') cut(a, b);
else puts(find(a) == find(b) ? "Yes" : "No");
}
return 0;
}
|