cogs1341 永无乡

---

打了一发替罪羊树。

鬼故事：替罪羊树去掉重构（变成裸的二叉排序树）依然跑得过= =

启发式合并。每次把小的里面所有东西往大的里面一丢，每个点最多被丢\(log_2n\)次（丢一次大小至少*2）

然后这题就写完了（替罪羊树很暴力，启发式合并也很暴力）

还要搞个并查集维护连通性，连通的就不用再合了。

（好像不兼容O2）

// It is made by XZZ

#include<cstdio>

#include<algorithm>

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

typedef long long ll;

il int gi(){

    rg int x=0;rg bool flg=0;rg char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return flg?-x:x;

}

const double alpha=0.723333;

const int maxn=100010;

int fa[maxn];

int siz[maxn],v[maxn],ch[maxn][2];

il int hd(int a){return a==fa[a]?a:fa[a]=hd(fa[a]);}

il int*_insert(int&x,const int&y){

    if(!x){x=y,siz[x]=1,ch[x][0]=ch[x][1]=0;return NULL;}

    ++siz[x];

    int*p=_insert(ch[x][v[y]>v[x]],y);

    if(alpha*siz[x]<max(siz[ch[x][0]],siz[ch[x][1]]))p=&x;

    return p;

}

int tot,res[maxn];

il vd _dfs(const int&x){if(x)_dfs(ch[x][0]),res[++tot]=x,_dfs(ch[x][1]);}

il vd redo(const int&x,const int &k){if(x)_dfs(ch[x][0]),_dfs(ch[x][1]),fa[x]=k;}

il int divide(int l,int r){

    if(l>r)return 0;

    int mid=(l+r)>>1;

    ch[res[mid]][0]=divide(l,mid-1);

    ch[res[mid]][1]=divide(mid+1,r);

    siz[res[mid]]=r-l+1;

    return res[mid];

}

il vd insert(int&x,const int&y){

    int*p=_insert(x,y);

    if(p){//这里if(p)改成if(0)就是裸的BST

        int&k=*p,s;

        tot=0,_dfs(k);

        if(k==x)s=divide(1,tot),fa[x]=x=fa[s]=s;

        else k=divide(1,tot);

    }

}

il vd dfs(const int&x,int&y){

    if(!x)return;

    dfs(ch[x][0],y),dfs(ch[x][1],y);

    insert(y,x);

}

il vd Union(int a,int b){

    int A=hd(a),B=hd(b);

    if(A==B)return;

    if(siz[A]>siz[B])dfs(B,A),fa[B]=A;

    else dfs(A,B),fa[A]=B;

}

int main(){

    int n=gi(),m=gi();

    rep(i,1,n)v[i]=gi(),siz[i]=1,fa[i]=i;

    while(m--)Union(gi(),gi());

    int q=gi();char opt[2];

    while(q--){

        scanf("%s",opt);

        if(opt[0]=='Q'){

            static int x,y;

            x=hd(gi()),y=gi();

            if(siz[x]<y){puts("-1");continue;}

            while(1){

                if(siz[ch[x][0]]+1==y){printf("%d\n",x);break;}

                if(y<=siz[ch[x][0]])x=ch[x][0];

                else y-=siz[ch[x][0]]+1,x=ch[x][1];

            }

        }else Union(gi(),gi());

    }

    return 0;

}