半年之后，我想回来拿此题练习一下 Splay。但是，我惊讶地发现自己半年前写的AC代码被自造的如下数据卡死循环了：

10 0
1 2 3 4 5 6 7 8 9 10 
4
B 3 2
B 5 1
B 5 2
Q 1 1

当时的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

long long n,m,t,tot,c[100100][2],f[100010],s[100100],w[100010],fa[100010],wtoid[100010];

long long chk(long long x){
	return c[f[x]][1]==x;
}
void refresh(long long x){
	s[x]=s[c[x][0]]+s[c[x][1]]+1;
}
void rotate(long long x){
	long long y=f[x],z=f[y],k=chk(x);
	c[y][k]=c[x][k^1],f[c[x][k^1]]=y;
	c[z][chk(y)]=x,f[x]=z;
	c[x][k^1]=y,f[y]=x;
	refresh(y),refresh(x);
} 
void splay(long long x,long long goal=0){
	long long y,z;
	while(f[x]!=goal){
		y=f[x],z=f[y];
		if(z!=goal) chk(x)^chk(y)?rotate(x):rotate(y);
		rotate(x);
	}
}
void add(long long x){
    w[++tot]=x;
    s[tot]=1;
    f[tot]=c[tot][0]=c[tot][1]=0;
}
void insert(long long x,long long root){
    long long p=root,fp=f[p];
    while(p && w[p]!=w[x]){
        fp=p;
        p=c[p][w[x]>w[p]];
    }
    if(!p){
        if(fp)
            c[fp][w[x]>w[fp]]=x;
        f[x]=fp;
    }
    splay(x);
}
long long kth(long long id,long long k){
	long long p=id;
	while(1){
		if(s[c[p][0]]+1<k){
			k-=(s[c[p][0]]+1);
			p=c[p][1];
		}
		else{
			if(s[c[p][0]]<k) return p;
			else p=c[p][0];
		}
	}
}
long long find(long long u){
	if(u==fa[u]) return u;
	return fa[u]=find(fa[u]);
}
void dfs(long long u,long long to){
	if(c[u][0]) dfs(c[u][0],to);
	if(c[u][1]) dfs(c[u][1],to);
	insert(u,to);
}
void join(long long u,long long v){
	long long fu=find(u),fv=find(v);
	if(fu!=fv) fa[fu]=fv;
	else return;
	splay(u),splay(v);
	if(s[u]>s[v]) swap(u,v);
	dfs(u,v);
}

int main(){
	long long i,j,u,v;
	char op;
	cin>>n>>m;
	for(i=1;i<=n;i++){
		cin>>u;
		wtoid[u]=i;
		add(u);
	}
	for(i=1;i<=n;i++) fa[i]=i;
	while(m--){
		cin>>u>>v;
		join(u,v);
	}
	cin>>t;
	while(t--){
		cin>>op>>u>>v;
		if(op=='Q'){
			splay(u);
			if(v>s[u]) cout<<-1<<endl;
			else cout<<kth(u,v)<<endl;
		}
		else if(op=='B'){
			join(u,v);
		}
	}
	return 0;
}

我实在是疑惑，不知道为何而卡死，求教诸位神仙。