P3377

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int value,k;
    Node *child=nullptr,*borth=nullptr;
};
Node* meld(Node* x,Node* y) {
    if(x==nullptr)return y;
    if(y==nullptr)return x;
    if(x->value > y->value)swap(x,y);
    y->borth = x->child;
    x->child = y;
    return x;
}
Node* insert(Node* x,int value) {
    Node* temp = new Node;
    temp->value = value;
    return meld(x,temp);
}
Node* merges(Node* x) {
    if(x==nullptr || x->borth==nullptr)
        return x;
    Node* y = x->borth;
    Node* c = y->borth;
    x->borth = y->borth = nullptr;
    return meld(merges(c),meld(x,y));
}
int cnt=0;
Node* pop(Node* x) {
    ++cnt;
    if(cnt==258) {
        int x;
        cout<<x;
    }
    Node *t = merges(x->child);
    delete x;
    return t;
}
unordered_map<int,Node*>node;
unordered_map<int,int>father;
unordered_map<int,int>is_die;
int find_root(int x) {
    if(father[x]==x)return x;
    return father[x] = find_root(father[x]);
}
Node* add(int x,int y) {
    int tx = find_root(x);
    int ty = find_root(y);
    father[tx] = ty;
    node[ty] = meld(node[tx],node[ty]);
    node[tx] = nullptr;
    return node[ty];
}
int main() {
    freopen("P3377_1.in","r",stdin);
    freopen("P3377_1.ans","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        father[i]=i;
        node[i] = insert(nullptr,x);
        node[i]->k = i;
    }
    while (m--) {
        int op,x,y;
        scanf("%d",&op);
        if(op==1) {
            scanf("%d%d",&x,&y);
            int tx = find_root(x);
            int ty = find_root(y);
            if(tx==ty || is_die[x]==1 || is_die[y]==1)continue;
            add(tx,ty);
        }
        else {
            scanf("%d",&x);
            if(x==-1) {
                printf("-1\n");
                cout<<flush;
                continue;
            }
            int tx = find_root(x);
            printf("%d\n",node[tx]->value);
            cout<<flush;
            int s = node[tx]->k;
            pop(node[tx]);
            is_die[s] = 1;
        }
    }
    return 0;
}