link_cut.cpp

// Link/Cut Tree
// Thiago Mota

#include <bits/stdc++.h>

using namespace std;
bool debug;

struct node{
    node *l, *r, *p;
    bool revert;
    int id;

    inline bool isRoot(){
        return !p || (p->l != this && p->r != this);
    }

    inline void flush(){
        if(!revert) return;
        revert = false;
        swap(l, r);

        if(l) l->revert ^= 1;
        if(r) r->revert ^= 1; 
    }
};

inline void connect(node* ch, node* p, int left){
    if(ch) ch->p = p;

    if(left==true) p->l = ch;
    else if(left==false) p->r = ch;
}

inline void rotate(node* x){
    node *p = x->p, *g = p->p;

    bool isRootP = p->isRoot();
    bool leftChild = (x == p->l);

    connect(leftChild?x->r:x->l, p, leftChild);
    connect(p, x, !leftChild);
    connect(x, g, isRootP ? -1 : p == g->l);
}

inline void splay(node* x){
    while(!x->isRoot()){
        node *p = x->p, *g = p->p;

        if(!p->isRoot())
            g->flush();
        p->flush();
        x->flush();

        if(!p->isRoot())
            rotate((x == p->l) == (p == g->l) ? p : x);
        rotate(x);
    }
    x->flush();
}

inline node* access(node* x){
    node* last = 0;
    for(node* y = x; y; y = y->p){
        splay(y);
        y->r = last;
        last = y;
    }
    splay(x);
    return last;
}

inline void makeRoot(node* x){
    access(x);
    x->revert ^= 1;
}

inline bool connected(node* x, node* y){
    if(x == y)
        return true;

    access(x);
    access(y);
    return x->p;
}

inline void link(node* u, node* v){
    if(connected(u, v)){
        if(debug) cerr << "ERROR: (" << u->id << ", " << v->id << ") are connected!\n";
        return;
    }

    makeRoot(u);
    u->p = v;
}

inline void cut(node* u, node* v){
    makeRoot(u);
    access(v);

    if(v->l != u || u->l || u->r){
        if(debug) cerr << "ERROR: no edge (" << u->id << ", " << v->id << ")\n";
        return;
    }

    v->l->p = 0;
    v->l = 0;
}

inline int scan(){
    int x = getchar_unlocked(), s=1, n=0;
    for(;x<'0'||x>'9';x=getchar_unlocked()) if(x=='-') s=-1;
    for(;x>='0'&&x<='9';x=getchar_unlocked()) n = 10*n + x - '0';
    return n*s;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    debug = false;
    n = scan(), m = scan();
    node** v = new node*[n+1];
    for(int i=0;i<=n;i++){
        v[i] = new node;
        v[i]->id = i;
    }

    for(int i=1;i<=m;i++){
        char c, aux;
        for(c=getchar_unlocked();c<'a'||c>'z';c=getchar_unlocked()) { }
        
        int a, b;
        a = scan(), b = scan();
        
        if(c == 'a'){
            link(v[a], v[b]);
            //if(debug) cerr << "LINK (" << a << ", " << b <<  ") answer: " << (connected(v[a], v[b])?"YES":"NO") << "\n";
        }else if(c == 'r'){
            cut(v[a], v[b]);
        }else{
            cout << (connected(v[a],v[b])?"YES":"NO") << "\n";
        }
    }
    return 0;
}