#include <iostream>
#include <fstream>
#include <list>
#include <limits>
#include <stdexcept>
#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) {
    if (other.rootList.empty()) return;

    rootList.merge(other.rootList, [](BinomialNode* a, BinomialNode* b) {
        return a->degree < b->degree;
    });

    auto prev = rootList.begin();
    auto curr = std::next(prev);
    auto next = std::next(curr);

    while (next != rootList.end()) {
        if ((*curr)->degree != (*prev)->degree || (next != rootList.end() && (*curr)->degree == (*next)->degree)) {
            prev = curr;
        } else if ((*curr)->key > (*prev)->key) {
            (*curr)->child = (*prev)->sibling;
            (*prev)->sibling = (*curr)->child;
            (*curr)->degree++;

            *prev = *curr;
        } else {
            (*prev)->child = (*curr)->sibling;
            (*curr)->sibling = (*prev)->child;
            (*prev)->degree++;

            *curr = *next;
            rootList.erase(next);
        }
        curr = std::next(prev);
        next = std::next(curr);
    }
}

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

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

    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);
    }
};

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 op;
        input >> op;

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

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

    return 0;
}