#include <fstream>
#include <vector>
#include <iostream>
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;
};

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 = nullptr;
        newNode->parent = nullptr;
        newNode->degree = 0;
        newNode->val = value;
        newNode->marked = false;
        return newNode;
    }
    void mergeWithRoot(node<V>* mergedNode){
        if (rootList == nullptr)
            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 == nullptr)
            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);
        parent->degree++;
        child->left = child->right = child;
        mergeWithChild(child, parent);

    }

    void cleanUp(){
        // magic number 128 = 64 bits x 2
        std::vector< node<V>* > degreeTable = {64, nullptr};
        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] != nullptr){
                node<V>* degNode = degreeTable[deg];

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

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

    void freeMemory(node<V>* x)
{
	if ( x != nullptr )
	{
		node<V>* t1 = x;
		do{
			node<V>* t2 = t1;
			t1 = t1->right;
			freeMemory(t2->child);
			delete t2;
		} while(t1 != x);
	}
}


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


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

        mergeWithRoot(insertedNode);

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

    void merge(FibonacciHeap<V>* other) {
        if (rootList == nullptr){
            rootList = other->rootList;
            maxNode = other->maxNode;
        }
        else if(other->rootList != nullptr) {

            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

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

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


    V extractMax(){
        node<V>* z = maxNode;
        V maxVal = 0;

        if (z != nullptr){
            if (z->child != nullptr) {
                std::vector<node<V> *> children = {};
                node<V> *currentChild = z->child;
                for (int t = 0; t < z->degree; t++) {
                    auto temp = currentChild;
                    children.push_back(temp);
                    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 = nullptr;
                rootList = nullptr;
            }
            else{
                maxNode = z->right;
                cleanUp();
            }

            maxVal = z->val;
            delete z;
        }
        return maxVal;
    }

};
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]);
            heapArray[mult2] = new FibonacciHeap<int>();
        }
    }
    return 0;
}