#include <fstream>
#include <vector>
#include <iostream>

struct node{
    int value;
    int degree;
    node *father, *child;
    node *next, *prev;

    explicit node(int value): value(value), degree(0), father(nullptr), child(nullptr), next(nullptr), prev(nullptr) {}
};

typedef node* FiboHeap;

void meld(FiboHeap& h1, FiboHeap& h2){
//    node *n1 = h1;
//    node *n2 = h2;
//    h1->next = h2;
//    h2->prev = h1;
//    n2->prev->next = n1->next;
//    n1->next->prev = n2->prev;
//    if(h1->value < h2->value)
//        h1 = h2;
    node *tail = h1->prev;
    h1->prev = h2->prev;
    h1->prev->next = h1;
    tail->next = h2;
    h2->prev = tail;
    if(h2->value > h1->value)
        h1 = h2;
}

void insert(FiboHeap& h, int value){
    node* n = new node(value);
    n->prev = n->next = n;
    if(h != nullptr)
        meld(h, n);
    else
        h = n;
}

void locateMax(FiboHeap& h){
    if(h != nullptr){
        node *maxNode = h;
        for(node *n = h->next; n != h; n = n->next){
            n->father = nullptr;
            if(n->value > maxNode->value)
                maxNode = n;
        }
        h = maxNode;
    }
}

void deleteMax(FiboHeap& h){
    node *root = h;
    if(h == h->next)
        h = h->child;
    else{
        h->prev->next = h->next;
        h->next->prev = h->prev;
        node *child = h->child;
        h = h->next;
        if(child != nullptr)
            meld(h, child);
    }
    locateMax(h);
    delete root;
}

int main(){
    std::ifstream fin("mergeheap.in");
    std::ofstream fout("mergeheap.out");

    int n, q, op, x, y;
    fin >> n >> q;

    std::vector<FiboHeap> h(n, nullptr);

    for( ; q; -- q){
        fin >> op;
        if(op == 1) {
            fin >> x >> y;
            insert(h[x - 1], y);
        }
        else if(op == 2){
            fin >> x;
//            fout << op << " " << x << "\n";
            fout << h[x - 1]->value << "\n";
            deleteMax(h[x - 1]);
        }
        else {
            fin >> x >> y;
            meld(h[x - 1], h[y - 1]);
            h[y - 1] = nullptr;
        }
//        for(int i = 0; i < n; i ++){
//            std::cout << i << ": " ;
//            if(h[i] != nullptr) {
//                std::cout << h[i]->value << " ";
//                for (node *nod = h[i]->next; nod != h[i]; nod = nod->next)
//                    std::cout << nod->value << " ";
//            }
//            std::cout << "\n";
//        }
//        std::cout << "\n";
    }

    return 0;
}