saf

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100000+10,maxm=1e6+10;
vector<int> hang[maxm];
vector<int> lie[maxm];
int rd[maxn],out[maxn],f[maxn];
struct Edge{
    int to,next,from;
}e[maxm<<2];
struct Node1{
    int to,next;
}g[maxm<<2];
struct Node{
    int x,y;
    int t;
}a[maxn];
int head[maxn],tot=0;
void Insert(int a,int b){
    e[++tot].to=b;
    e[tot].from=a;
    e[tot].next=head[a];
    head[a]=tot;
}
int rhead[maxn],top=0;
void add(int a,int b){
    g[++top].to=b;
    g[top].next=rhead[a];
    rhead[a]=top;
}
int dfn[maxn],low[maxn],size[maxn],st[maxn],t=0,sc=0,scc[maxn],vis[maxn],Time=0;
void tarjan(int u){
    dfn[u]=low[u]=++Time;
    st[++t]=u;
    vis[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        sc++;
        while(st[t]!=u){
            scc[st[t]]=sc;
            size[sc]++;
            vis[st[t]]=0;
            t--;
        }
        scc[u]=sc;
        size[sc]++;
        vis[u]=0;
        t--;
    }
}
void tosort(){
    queue<int> q;
    for(int i=1;i<=sc;i++){
        if(!rd[i]){
            q.push(i);
            f[i]=size[i];
        }    
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=rhead[u];i;i=g[i].next){
            int v=g[i].to;
            rd[v]--;
            f[v]=max(f[v],f[u]+size[v]);
            if(!rd[v]){
                q.push(v);
            }
        }
    }
}
int main(){
    int n,r,c;
    scanf("%d%d%d",&n,&r,&c);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
        hang[a[i].x].push_back(i);
        lie[a[i].y].push_back(i);
    }    
    for(int i=1;i<=n;i++){
        if(a[i].t==1){
            int size=hang[a[i].x].size();
            for(int j=0;j<size;j++){
                int x=hang[a[i].x][j];
                if(x==i) continue;
                Insert(i,x);
            }    
        }
        else if(a[i].t==2){
            int size=lie[a[i].y].size();
            for(int j=0;j<size;j++){
                int x=lie[a[i].y][j];
                if(x==i) continue;
                Insert(i,x);
            }
        }
        else{
            for(int k=-1;k<=1;k++){
                int x=a[i].x+k;
                int size=hang[x].size();
                for(int j=0;j<size;j++){
                    int xx=hang[x][j];
                    if(xx==i||a[xx].y<a[i].y-1||a[xx].y>a[i].y+1) continue;
                    Insert(i,xx);
                }
            }
        }
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=tot;i++){
        int u=e[i].from;
        int v=e[i].to;
        if(scc[u]!=scc[v]){
            add(scc[u],scc[v]);
            rd[scc[v]]++;
            out[scc[u]]++;
        }    
    }
    tosort();
    int ans=0;
    for(int i=1;i<=sc;i++){
        if(!out[i]) ans=max(ans,f[i]);
    }
    printf("%d
",ans);
    return 0;
}

#include<cstdio>
#include<cstring>
#include<utility>
using namespace std;
const int maxn=250000+10;
int lazy[maxn<<2],tree[maxn<<2];
struct Edge{
    int to,next;
}e[maxn<<1];
int head[maxn],tot=0;
void Insert(int a,int b){
    e[++tot].to=b;
    e[tot].next=head[a];
    head[a]=tot;
}
int top=0;
int deep[maxn],size[maxn],num[maxn];
void dfs(int u,int fa){
    deep[u]=deep[fa]+1;
    num[u]=++top;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        size[u]+=size[v];
    }
}
void pushup(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void Modify(int rt,int l,int r,int x,int w){
    if(l==r){
        tree[rt]+=w;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) Modify(rt<<1,l,mid,x,w);
    else Modify(rt<<1|1,mid+1,r,x,w);
    pushup(rt);
}
void update(int rt,int l,int r,int w){
    tree[rt]+=(r-l+1)*w;
    lazy[rt]+=w;
}
void pushdown(int rt,int l,int r){
    int mid=(l+r)>>1;
    update(rt<<1,l,mid,lazy[rt]);
    update(rt<<1|1,mid+1,r,lazy[rt]);
    lazy[rt]=0;
}
int query(int rt,int l,int r,int x){
    if(l==r){
        return tree[rt];
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) return query(rt<<1,l,mid,x);
    else return query(rt<<1|1,mid+1,r,x);
}
void Modify1(int rt,int l,int r,int s,int t,int w){
    if(s<=l&&t>=r){
        update(rt,l,r,w);
        return;
    }
    int mid=(l+r)>>1;
    if(s<=mid) Modify1(rt<<1,l,mid,s,t,w);
    if(t>mid) Modify1(rt<<1|1,mid+1,r,s,t,w);
    pushup(rt);
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        Insert(x,y);
        Insert(y,x);
    }
    for(int i=1;i<=n;i++) size[i]=1;
    dfs(1,0);
    for(int i=1;i<=n;i++) Modify(1,1,n,num[i],deep[i]-1);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=n+m-1;i++){
        char s[3];
        scanf("%s",s);
        if(s[0]=='W'){
            int x;
            scanf("%d",&x);
            int ans=query(1,1,n,num[x]);
            printf("%d
",ans);
        }
        else{
            int x,y;
            scanf("%d%d",&x,&y);
            if(x>y) swap(x,y);
            Modify1(1,1,n,num[y],num[y]+size[y]-1,-1);
        }
    }
    return 0;
}