#include <iostream>
#include <list>
#include <limits>
#include <stdexcept>
#include <fstream>
#include <vector>

struct BinomialNode {
    int key;
    int degree;
    BinomialNode* parent;
    BinomialNode* child;
    BinomialNode* sibling;
};

class BinomialHeap {
private:
    std::list<BinomialNode*> rootList;

    BinomialNode* newNode(int key) {
        BinomialNode* node = new BinomialNode;
        node->key = key;
        node->degree = 0;
        node->parent = nullptr;
        node->child = nullptr;
        node->sibling = nullptr;
        return node;
    }

    BinomialNode* mergeTrees(BinomialNode* a, BinomialNode* b) {
        if (a->key > b->key) std::swap(a, b);
        b->sibling = a->child;
        a->child = b;
        a->degree++;
        return a;
    }

    void mergeRootLists(BinomialHeap& other) {
        rootList.splice(rootList.end(), other.rootList);
        if (rootList.empty()) return;
        for (auto it1 = rootList.begin(), it2 = std::next(it1), it3 = rootList.end(); it2 != rootList.end();) {
            if ((*it1)->degree < (*it2)->degree) {
                it1 = it2++;
                continue;
            }
            if (it3 != rootList.end() && (*it3)->degree == (*it1)->degree) {
                it1 = rootList.erase(it1);
            } else {
                *it1 = mergeTrees(*it1, *it2);
                it2 = rootList.erase(it2);
            }
            it3 = it2;
            if (it3 != rootList.end()) ++it3;
        }
    }

public:
    bool isEmpty() const {
        return rootList.empty();
    }

    void insert(int key) {
        BinomialHeap tempHeap;
        tempHeap.rootList.push_back(newNode(key));
        mergeRootLists(tempHeap);
    }

    int getMin() {
        if (isEmpty()) throw std::runtime_error("Heap is empty.");
        int minKey = std::numeric_limits<int>::max();
        for (const auto& root : rootList) {
            if (root->key < minKey) {
                minKey = root->key;
            }
        }
        return minKey;
    }

    int extractMin() {
        if (isEmpty()) throw std::runtime_error("Heap is empty.");
        auto minRoot = rootList.begin();
        for (auto it = rootList.begin(); it != rootList.end(); ++it) {
            if ((*it)->key < (*minRoot)->key) {
                minRoot = it;
            }
        }
        int minKey = (*minRoot)->key;
        BinomialNode* minNodeChild = (*minRoot)->child;
        rootList.erase(minRoot);

        BinomialHeap tempHeap;
        while (minNodeChild) {
            BinomialNode* sibling = minNodeChild->sibling;
            minNodeChild->sibling = nullptr;
            minNodeChild->parent = nullptr;
            tempHeap.rootList.push_front(minNodeChild);
            minNodeChild = sibling;
        }
        mergeRootLists(tempHeap);
        return minKey;
    }
     int getMax() {
        if (isEmpty()) throw std::runtime_error("Heap is empty.");
        int maxKey = std::numeric_limits<int>::min();
        for (const auto& root : rootList) {
            if (root->key > maxKey) {
                maxKey = root->key;
            }
        }
        return maxKey;
    }

    int extractMax() {
        if (isEmpty()) throw std::runtime_error("Heap is empty.");
        auto maxRoot = rootList.begin();
        for (auto it = rootList.begin(); it != rootList.end(); ++it) {
            if ((*it)->key > (*maxRoot)->key) {
                maxRoot = it;
            }
        }
        int maxKey = (*maxRoot)->key;
        BinomialNode* maxNodeChild = (*maxRoot)->child;
        rootList.erase(maxRoot);

        BinomialHeap tempHeap;
        while (maxNodeChild) {
            BinomialNode* sibling = maxNodeChild->sibling;
            maxNodeChild->sibling = nullptr;
            maxNodeChild->parent = nullptr;
            tempHeap.rootList.push_front(maxNodeChild);
            maxNodeChild = sibling;
        }
        mergeRootLists(tempHeap);
        return maxKey;
    }
    void merge(BinomialHeap& other) {
        mergeRootLists(other);
        other.rootList.clear();
    }
};


  int main() {
    std::ifstream input("mergeheap.in");
    std::ofstream output("mergeheap.out");

    int N, Q;
    input >> N >> Q;

    std::vector<BinomialHeap> heaps(N);

    for (int i = 0; i < Q; ++i) {
        int operation;
        input >> operation;

        if (operation == 1) {
            int m, x;
            input >> m >> x;
            heaps[m - 1].insert(x);
        } else if (operation == 2) {
            int m;
            input >> m;
            int maxElement = heaps[m - 1].extractMax();
            output << maxElement << std::endl;
        } else if (operation == 3) {
            int a, b;
            input >> a >> b;
            heaps[a - 1].merge(heaps[b - 1]);
        }
    }

    input.close();
    output.close();

    return 0;
}