1 #include
     
       2 using namespace std; 3 const int N=100010; 4 int n,m,v[N],color[N],root[N],lc[N],rc[N],dis[N]; 5 bool vis[N]; 6 int find(int k){
   return color[k]==k?k:color[k]=find(color[k]);} 7 inline void matain(int k){ 8     if(dis[rc[k]]>dis[lc[k]]) swap(lc[k],rc[k]); 9     dis[k]=dis[lc[k]]+1;10     return;11 }12 int marge(int a,int b){13     if(!a) return b;14     if(!b) return a;15     if(v[a]>v[b]) swap(a,b);16     rc[a]=marge(rc[a],b);17     matain(a);18     return a;19 }20 int pop(int k){21     if(vis[k]) return -1;22     int ck=find(k),ans=v[root[ck]];23     vis[root[ck]]=1;24     root[ck]=marge(lc[root[ck]],rc[root[ck]]);25     return ans;26 }27 int main(){28     int opt,t1,t2,c1,c2;29     scanf("%d%d",&n,&m);30     for(int i=1;i<=n;i++) scanf("%d",&v[i]),root[i]=color[i]=i;31     while(m--){32         scanf("%d%d",&opt,&t1);33         if(opt==1){34             scanf("%d",&t2);35             c1=find(t1),c2=find(t2);36             if(c1!=c2&&!vis[t1]&&!vis[t2]){37                 root[c1]=marge(root[c1],root[c2]);38                 color[c2]=c1;39             }40         }else{41             printf("%d\n",pop(t1));42         }43     }44     return 0;45 }