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

using namespace std;

class Node{
public:
    int value;
    Node* parent;
    Node* left;
    Node* right;
    Node* child;
    bool marked;
    int degree;
    bool seen;
    Node(int val);
    Node();
    friend ostream& operator <<(ostream& out, const Node&);
    Node& operator =(const Node&);
};
ostream& operator <<(ostream& out, const Node& n){
    cout<<"============NODE============";
    cout<<"VALUE: "<<n.value<<" ";
    if(n.parent != nullptr)
        cout<<"PARENT: "<<n.parent->value<<" ";
    if(n.right != nullptr)
        cout<<"RIGHT: "<<n.right->value<<" ";
    if(n.child != nullptr)
        cout<<"CHILD: "<<n.child->value<<" ";
    if(n.left != nullptr)
        cout<<"LEFT: "<<n.left->value<<endl;

    return out;
}
Node::Node(int val){
    this->value = val;
    this->parent = nullptr;
    this->child = nullptr;
    this->right = this;
    this->left = this;
    this->marked = false;
    this->seen = false;
    int degree = 0;
}
Node::Node(){
    this->value = 0;
    this->parent = nullptr;
    this->child = nullptr;
    this->right = this;
    this->left = this;
    this->marked = false;
    this->seen = false;
    int degree = 0;
}
Node& Node::operator=(const Node& node){
    if(this != &node){
        this->value = node.value;
        this->parent = node.parent;
        this->left = node.left;
        this->right = node.right;
        this->child = node.child;
        this->marked = node.marked;
        this->degree = node.degree;
        this->seen = node.seen;
    }
    return *this;
}

class FibonacciHeap{
    Node* maxNode;
    Node* head;
    int size = 0;
public:
    FibonacciHeap(){ this->maxNode = nullptr; this->head = nullptr; }
    FibonacciHeap(int size, Node* max, Node* H){
        this->size = size;
        this->maxNode = max;
        this->head = H;
    }
    void insert(int val){
        Node* n = new Node;
        n->value = val;
        n->left = n;
        n->right = n;
        n->parent = nullptr;
        n->child = nullptr;
        n->degree = 0;
        n->seen = false;
        n->marked = false;
        if(this->maxNode == NULL){
            this->maxNode = n;
            this->head = n;
        } else {
            Node* last = this->head->left;

            n->right = head;
            n->left = last;
            last->right = n;
            head->left = n;

            if(this->maxNode->value < n->value) this->maxNode = n;
        }
        this->size+=1;
    }

    void getMax(){
        if(this->maxNode != nullptr){
            cout<<"max: "<<this->maxNode->value<<":::::::";
        } else {
            cout<<"max doesn't exist!"<<endl;
        }
    }

    Node* find(int val){
        return this->findNode(val, this->head);
    }
    Node* findNode(int val, Node* n){
        if(n->value == val) return n;
        if(n->right != nullptr){
            if(n->right->seen == false){
                n->right->seen = true;
                Node* foundNode = findNode(val, n->right);
                n->right->seen = false;
                if(foundNode != nullptr) return foundNode;
            }
        }
        if(n->child != nullptr){
            if(n->child->seen == false){
                n->child->seen = true;
                Node* foundNode2 = findNode(val, n->child);
                n->child->seen = false;
                if(foundNode2 != nullptr) return foundNode2;
            }
        }
    }

    FibonacciHeap& heapUnion(FibonacciHeap& heap2) {
        if(heap2.maxNode->value > this->maxNode->value){
            this->maxNode = heap2.maxNode;
        }

        Node* last = heap2.head->left;
        Node* first = this->head;
        Node* lastOfFirst = this->head->left;
        Node* firstOfSecond = heap2.head;

        firstOfSecond->left = lastOfFirst;
        last->right = first;
        lastOfFirst->right = firstOfSecond;
        first->left = last;

        this->size += heap2.size;

        return *this;
    }

    void extractToRootList(Node* node){
        if(this->head == nullptr){
            this->head = node;
        }

        Node* last = this->head->left;

        node->right = head;
        node->left = last;
        head->left = node;
        last->right = node;

        node->parent = nullptr;

    }
    void extractChildrenToRootList(Node* child){
//        this->showHeap();
        Node* lastChild = child->left;
        Node* last = this->head->left;

        lastChild->right = head;
        child->left = last;
        head->left = lastChild;
        last->right = child;

        child->parent->child = nullptr;
        Node* loop = child;
        while(loop->parent != nullptr){
            loop->parent = nullptr;
            loop = loop->right;
        }
//        cout<<endl;this->showHeap();cout<<endl;
    }
    void consolidate(Node* H){
        vector<Node*> A = {}, uncheck = {};
        for(int i=0; i<this->size; i++){
            A.push_back(nullptr);
        }
        int d;
        Node* w = this->head;
        while(w->seen == false){
            w->seen = true;
            Node* next = w->right;
            uncheck.push_back(w);
            Node* x = w;
            int d = x->degree;
            bool i = 0;
            while(A[d] != nullptr){
                Node* y = A[d];
                if(x->value < y->value) {
                    Node *aux = x;
                    x = y;
                    y = aux;
                }
                this->link(this->head, y, x);
                A[d] = nullptr;
                d = d + 1;
            }
            A[d] = x;
            w = next;
        }

        for(int i=0; i<uncheck.size(); i++){
            uncheck[i]->seen = false;
        }
        this->maxNode = nullptr; // ????????
        this->head = nullptr;
        for(int i=0; i<A.size(); i++){
            if(A[i] != nullptr){
                this->extractToRootList(A[i]);
                if(this->maxNode == nullptr || A[i]->value > this->maxNode->value){
                    this->maxNode = A[i];
                }
            }
        }
    }
    void link(Node* node, Node* y, Node* x){
        // remove y from root list
        Node* left = y->left;
        Node* right = y->right;
        left->right = right;
        right->left = left;

            // make y child of x
            if(x->child != nullptr){
                Node* child = x->child;
                Node* last = child->left;
                y->right = child;
                y->left = last;
                last->right = y;
                child->left = y;
                y->parent = x;
            } else {
                x->child = y;
                y->parent = x;
                y->left = y;
                y->right = y;
            }
        x->degree++;
        y->marked = false;
    }
    Node* extractMax(){
        Node* z = this->maxNode;
        if(z != nullptr){
            if(z->child != nullptr) {
                this->extractChildrenToRootList(z->child);
            }
            this->removeMax();
            if(z == z->right){
                if(this->head == z) this->head = nullptr;
                this->maxNode = nullptr;
            }
            else {
                if(this->head == maxNode) this->head = z->right;
                this->maxNode = z->right;
                this->consolidate(this->head);
            }
            this->size--;
        }
        return z;
    }

    void removeMax(){
        Node* left = this->maxNode->left;
        Node* right = this->maxNode->right;
        left->right = right;
        right->left = left;
    }

    void showHeap(Node* parent = NULL, Node* node = NULL){
        if(this->head == nullptr){
            cout<<"HEAP EMPTY!"<<endl;
            return;
        }
        if(node == NULL) node = this->head;
        node->seen = true;
        if(parent != NULL) cout<<"p: "<<parent->value<<" c: "<<node->value<<" ";
        else cout<<"node: "<<node->value<<" ";

        if(node->right != NULL) {
            if (!node->right->seen) {
                this->showHeap(parent, node->right);
            }
        }
        if(node->child != NULL) {
            if (!node->child->seen) {
                this->showHeap(node, node->child);
            }
        }
        node->seen = false;
    }
    FibonacciHeap& operator=(const FibonacciHeap& fh){
        if(this!=&fh){
            if(fh.head != nullptr){
                this->head = fh.head;
            }
            if(fh.maxNode != nullptr){
                this->maxNode = fh.maxNode;
            }
            this->size = fh.size;
        }
        return *this;
    };
};

int main()
{

    ifstream f("mergeheap.in");
    ofstream g("mergeheap.out");
    int N, Q, a, b, c;
    vector<FibonacciHeap*> heaps;
    f>>N; f>>Q;
    for(int i=0; i<=N; i++){
        FibonacciHeap heap;
        heaps.push_back(new FibonacciHeap);
    }

    while(Q>0){
        f>>a;
        if(a == 2) f>>b;
        else f>>b>>c;
        switch(a){
            case 1: {
                heaps[b]->insert(c);
                break;
            }
            case 2: {
                Node* Max = heaps[b]->extractMax();
                g<<Max->value<<endl;
                break;
            }
            case 3: {
                *heaps[b] = heaps[b]->heapUnion(*heaps[c]);
                heaps[c] = new FibonacciHeap();
                break;
            }
            default: {
                break;
            }
        }
        Q--;
    }
    f.close();
    g.close();
    return 0;
}