又红又黑的

#include<bits/stdc++.h>
#define N 100500
using namespace std;
int n,q,opt,x,y;
int val[N],f[N];bool vis[N];
int Right[N],son[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int Union(int x,int y)
{
    if(vis[x]||vis[y]||x==y||!x)    return 0;
    if(!y)  return x;
    if(x>y) swap(x,y);
    if(val[x]>val[y])   swap(x,y);
    Right[y]=son[x];
    son[x]=y;   f[y]=x;
    return x;
}
int pairing(int x)
{
    int r=Right[x];
    if(!r)  return x;
    return Union(Union(x,r),pairing(Right[r]));
    //find(x);
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        f[i]=i;
    }
    while(q--)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d",&x,&y);
            Union(find(x),find(y));
        }
        else
        {
            scanf("%d",&x); x=find(x);
            f[son[x]]=son[x];
            vis[x]=1;   pairing(Right[x]);
            printf("%d\n",val[x]);
        }
    }
}