#include <fstream>
#include <vector>

std::ifstream f("mergeheap.in");
std::ofstream g("mergeheap.out");

///                       -----
///     FIBONACCI HEAP de MAXIM !
///                       -----


template <class V> class FibonacciHeap;

const double INF_fibonacci_heap = 2000000001;

template <class V> struct node {
    node<V>* left;
    node<V>* right;
    node<V>* child;
    node<V>* parent;
    V val;
    bool marked;
    int degree;
    /*
    node(V value){
        left = this;
        right = this;
        child = NULL;
        parent = NULL;
        degree = 0;
        val = value;
        marked = false;
    }
     */
};

template <class V> class FibonacciHeap{
private:
    node<V>* maxNode;
    node<V>* rootList;


    node<V>* constructNode(V value){
        auto* newNode = new node<V>;
        newNode->left = newNode;
        newNode->right = newNode;
        newNode->child = NULL;
        newNode->parent = NULL;
        newNode->degree = 0;
        newNode->val = value;
        newNode->marked = false;
        return newNode;
    }
    void mergeWithRoot(node<V>* mergedNode){
        if (rootList == NULL)
            rootList = mergedNode;
        else {
            rootList->left->right = mergedNode;
            mergedNode->left = rootList->left;
            mergedNode->right = rootList;
            rootList->left = mergedNode;
        }
    }

    void removeFromRoot(node<V>* removedNode){
        if (removedNode == rootList)
            rootList = removedNode->right;
        removedNode->left->right = removedNode->right;
        removedNode->right->left = removedNode->left;
    }

    void removeFromChildren(node<V>* removedChild, node<V>* parent){
        if (parent->child == parent->child->right)
            parent->child = NULL;
        else if (parent->child == removedChild) {
            parent->child = removedChild->right;
            removedChild->right->parent = parent;
        }
        removedChild->left->right = removedChild->right;
        removedChild->right->left = removedChild->left;

    }

    void mergeWithChild(node<V>* newChild, node<V>* parent){
        if (parent->child == NULL)
            parent->child = newChild;
        else{
            // Inserez mereu la dreapta primului copil
            newChild->right = parent->child->right;
            newChild->left = parent->child;
            parent->child->right->left = newChild;
            parent->child->right = newChild;
        }
    }

    void heapLink(node<V>* child, node<V>* parent){
        removeFromRoot(child);
        child->left = child->right = child;
        mergeWithChild(child, parent);

    }

    void cleanUp(){
        // magic number 128 = 64 bits x 2
        std::vector< node<V>* > degreeTable = {128, NULL};
        std::vector< node<V>* > rootNodes = {rootList};
        node<V>* p = rootList->right;
        while (p != rootList) {
            rootNodes.push_back(p);
            p = p->right;
        }
        for (auto rootNode : rootNodes){
            int deg = rootNode->degree;
            while(degreeTable[deg] != NULL){
                node<V>* degNode = degreeTable[deg];

                if(rootNode->val < degNode ->val)
                    std::swap(rootNode, degNode);

                heapLink(degNode, rootNode);
                degreeTable[deg] = NULL;
                deg++;
            }
            degreeTable[deg] = rootNode;
        }
        for(int i = 0; i < 128; i++)
            if (degreeTable[i] != NULL)
                if( degreeTable[i]->val > maxNode->val)
                    maxNode = degreeTable[i];
    }

    void cut(node<V>* removedChild, node<V>* parent){
        removeFromChildren(removedChild, parent);
        parent->degree -= 1;
        mergeWithRoot(removedChild);
        removedChild->parent = NULL;
        removedChild->marked = false;
    }

    void cascadingCut(node<V>* currentNode){
        node<V>* currentParent = currentNode->parent;
        if (currentParent != NULL) {
            if (!currentNode->marked)
                currentNode->marked = true;
            else {
                cut(currentNode, currentParent);
                cascadingCut(currentParent);
            }
        }
    }



public:
    FibonacciHeap(){
        maxNode = NULL;
        rootList = NULL;
    }
    ~FibonacciHeap() = default;

    void insert(V insertedValue){
        node<V>* insertedNode = constructNode(insertedValue);

        mergeWithRoot(insertedNode);

        if (maxNode == NULL || maxNode->val < insertedValue)
            maxNode = insertedNode;
    }

    void merge(FibonacciHeap<V>* other) {
        if (rootList == NULL){
            rootList = other->rootList;
            maxNode = other->maxNode;
        }
        else {
            node<V> *last = other->rootList->left;   // ultimul nod dupa merge
            other->rootList->left = rootList->left;  // rootList->left = ultimul din primul heap
            rootList->left->right = other->rootList; // ult din primul heap ->left = other.rootList
            rootList->left = last;                  // rootList->left = ultimul nod dupa merge
            rootList->left->right = rootList;       // ultimul nod dupam merge ->right = rootList

            // minNode = max(minNode, other.minNode)
            if (maxNode->val < other->maxNode->val)
                maxNode = other->maxNode;
        }
    }

    V getMaximum(){
        return maxNode->val;
    };


    V extractMax(){
        node<V>* z = maxNode;
        if (maxNode != NULL){
            if (z->child != NULL) {
                std::vector<node<V> *> children = {};
                node<V> *currentChild = z->child;
                for (int t = 0; t < z->degree; t++) {
                    children.push_back(currentChild);
                    currentChild = currentChild->right;
                }
                for (auto child: children)
                    mergeWithRoot(child);
            }

            removeFromRoot(z);

            if (z == z->right){
                // Am extras dintr-un heap cu un singur element (care era si minim)
                maxNode = NULL;
                rootList = NULL;
            }
            else{
                maxNode = z->right;
                cleanUp();
            }
        }
        return z->val;
    }

    void increaseValue(node<V>* incNode, V incValue){
        if (incValue < incNode->val)
            return;
        incNode->val = incValue;
        node<V>* parentNode = incNode->parent;
        if (parentNode != NULL && incNode->val > parentNode->val){
            cut(incNode, parentNode);
            cascadingCut(parentNode);
        }
        if (incValue > maxNode->val)
            maxNode = incNode;

    }

    node<V>* deleteNode(node<V>* delNode){
        decreaseValue(delNode, INF_fibonacci_heap);
        return extractMax();
    }

};
int main() {
    int N,Q;
    std::vector< FibonacciHeap<int>* > heapArray;
    f >> N >> Q;
    for(int i = 0; i < N + 1; ++i)
    {
        heapArray.push_back(new FibonacciHeap<int>());
    }
    for(int i = 0; i < Q; ++i)
    {
        int tipOperatie;
        f >> tipOperatie;
        if (tipOperatie == 1){
            int multime, val;
            f >> multime >> val;
            heapArray[multime]->insert(val);
        }
        else if (tipOperatie == 2){
            int multime;
            f >> multime;
            g << heapArray[multime]->extractMax() << "\n";
        }
        else if (tipOperatie == 3){
            int mult1, mult2;
            f >> mult1 >> mult2;
            heapArray[mult1]->merge(heapArray[mult2]);
        }
    }
    return 0;
}