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

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

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 p){
    auto n = new node;
    n->value = p;
    n->degree = 0;
    n->father = n->child = nullptr;
    n->next = n->prev = n;
    if(h != nullptr)
        meld(h, n);
    else
        h = n;
}

void locateMax(FiboHeap& h){
    if(h != nullptr) {
//        h->father = 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::cout << "Stuck here\n";
    std::vector <node*> rank(maxDegree(h) + 1, nullptr);
    rank[h->degree] = h;
    for(node *n = h->next; n != h; n = n->next){
        while(n->degree < rank.size() - 1 && rank[n->degree] != nullptr){
            merge(n, rank[n->degree]);
            rank[n->degree - 1] = nullptr;
        }
        if(n->degree == rank.size() - 1)
            rank.push_back(n);
        else
            rank[n->degree] = n;
    }
//    std::cout << "Hey there\n";
}

void deleteMax(FiboHeap& h){
    node *root = h;
//    std::cout << "h: " << h->value << "\n";
    if(h == h->next)
        h = h->child;
    else if(h->child == nullptr){
        h->prev->next = h->next;
        h->next->prev = h->prev;
        h = h->next;
    } else {
        h->prev->next = h->child;
        h->next->prev = h->child->prev;
        h->child->prev = h->prev;
        h->next->prev->next = h->next;
        h = h->child;
    }
//    if(h != nullptr)
//        std::cout << "before locateMax: " << h->value << "\n";
    locateMax(h);
//    std::cout << "hi hi\n";
    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> heaps(n, nullptr);

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