#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 *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;
    }
}

int maxDegree(FiboHeap& h){
    int rank = h->degree;
    for(node *n = h->next; n != h; n = n->next)
        if(n->degree > rank)
            rank = n->degree;
    return rank;
}


void merge(FiboHeap& n1, FiboHeap& n2){
//    std::cout << n1->value << " " << n2->value << "\n";
    if(n1->value < n2->value){
        merge(n2, n1);
        n1 = n2;
    } else{
        n1->degree ++;
        n2->prev->next = n2->next;
        n2->next->prev = n2->prev;
        n2->father = n1;
        if(n1->child != nullptr){
            n2->prev = n1->child->prev;
            n2->next = n1->child;
            n1->child->prev = n2;
            n2->prev->next = n2;
        } else {
            n2->prev = n2->next = n2;
            n1->child = n2;
        }
    }
}

void consolidate(FiboHeap& h){
    std::vector<node *> rank(maxDegree(h) + 1, nullptr);
    rank[h->degree] = h;
    bool gasit = false;
    do{
        gasit = false;
        for(node *n = h->next; n != h; n = n->next) {
            if (n->degree < rank.size() - 1 && rank[n->degree] != nullptr) {
                merge(n, rank[n->degree]);
                rank[n->degree - 1] = nullptr;
                gasit = true;
            }
            if (n->degree == rank.size() - 1)
                rank.push_back(n);
            else if(rank[n->degree] == nullptr)
                rank[n->degree] = n;
        }
    } while(gasit);
}

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;
}