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
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;

namespace fast_io {
    //...
}using namespace fast_io;

const int MAXN = 20000;

struct Link_Cat_Tree{
    int f[MAXN],c[MAXN][2];
    bool rev[MAXN];
    inline bool noroot(int x){
        return (c[f[x]][0] == x) || (c[f[x]][1] == x);
    }
    inline void reverse(int x){
        if(!x)  return;
        swap(c[x][0],c[x][1]);
        rev[x] ^= 1;
    }
    inline void push_down(int x){
        if(!x) return;
        if(rev[x]){
            reverse(c[x][0]),reverse(c[x][1]);
            rev[x] = 0;
        }
    }
    void push_all(int x){
        if(!x) return;
        if(noroot(x)) push_all(f[x]);
        push_down(x);
    }
    inline void rotate(int x){
        int y = f[x],z = f[y],t = (c[y][1] == x),w = c[x][1-t];
        if(noroot(y)) c[z][c[z][1] == y] = x;
        c[y][t] = w,c[x][1-t] = y;  
        if(w) f[w] = y;
        f[y] = x,f[x] = z;
    }
    inline void splay(int x){
        push_all(x);
        while(noroot(x)){
            int y = f[x],z = f[y];
            if(noroot(y)){
                if((c[z][1] == y) ^ (c[y][1] == x))
                    rotate(x);
                else rotate(y);
            }rotate(x);
        }
    }
    inline void access(int x){
        for(int y = 0;x;x = f[y=x])
            splay(x),c[x][1] = y;
    }
    inline void makeroot(int x){
        access(x);splay(x);reverse(x);
    }
    inline int find(int x){
        access(x),splay(x);
        push_down(x);
        while(c[x][0])
            x = c[x][0],push_down(x);
        return x;
    }
    inline void link(int x,int y){
        makeroot(x);
        if(find(y)!=x)
            f[x] = y;
    }
    inline void cat(int x,int y){
        makeroot(x);
        if(find(y) == x && f[x] == y && !c[x][1])
            f[x] = c[y][0] = 0;
    }
    inline int query(int x,int y){
        return int(find(x) == find(y));
    }
};

Link_Cat_Tree S;

int n,m;

char yes[6] = "Yes\n",no[5] = "No\n";

void solve(){
    read(n),read(m);
    char op[20];int a,b;
    for(int i = 1;i<=m;i++){
        read(op);read(a),read(b);
        if(op[0] == 'C')
            S.link(a,b);
        if(op[0] == 'D')
            S.cat(a,b);
        else if(op[0] == 'Q')
            print(S.query(a,b) ? yes:no);
    }
}

int main(){
    solve();
    flush();
    return 0;
}