#include <iostream>
#include <vector>
#include <string>
#include <cstdio>

/**
 * Node structure for the Pairing Heap.
 * Uses Left-Child Right-Sibling representation for O(1) merge and efficient pop.
 */
struct Node {
    int value;
    Node *child;
    Node *sibling;

    Node(int val) : value(val), child(nullptr), sibling(nullptr) {}
};

/**
 * Merges two Max-Pairing Heaps.
 */
Node* merge(Node* h1, Node* h2) {
    if (!h1) return h2;
    if (!h2) return h1;

    if (h1->value >= h2->value) {
        h2->sibling = h1->child;
        h1->child = h2;
        return h1;
    } else {
        h1->sibling = h2->child;
        h2->child = h1;
        return h2;
    }
}

/**
 * Performs the two-pass merging strategy iteratively.
 */
Node* combineSiblings(Node* firstSibling) {
    if (!firstSibling) return nullptr;
    if (!firstSibling->sibling) return firstSibling;

    // Pass 1: Merge pairs from left to right
    std::vector<Node*> pairs;
    Node* current = firstSibling;
    while (current) {
        Node* h1 = current;
        Node* h2 = current->sibling;

        if (h2) {
            Node* nextBatch = h2->sibling;
            h1->sibling = h2->sibling = nullptr; // Isolate
            pairs.push_back(merge(h1, h2));
            current = nextBatch;
        } else {
            h1->sibling = nullptr;
            pairs.push_back(h1);
            break;
        }
    }

    // Pass 2: Merge pairs from right to left
    Node* root = pairs.back();
    for (int i = (int)pairs.size() - 2; i >= 0; --i) {
        root = merge(root, pairs[i]);
    }
    return root;
}

class MergeHeapProblem {
private:
    std::vector<Node*> heaps;
    std::string in_file;
    std::string out_file;

public:
    MergeHeapProblem(const std::string& prefix) {
        in_file = prefix + ".in";
        out_file = prefix + ".out";
    }

    void solve() {
        FILE* fin = fopen(in_file.c_str(), "r");
        if (!fin) return;

        FILE* fout = fopen(out_file.c_str(), "w");
        if (!fout) {
            fclose(fin);
            return;
        }

        int num_heaps, num_ops;
        if (fscanf(fin, "%d %d", &num_heaps, &num_ops) != 2) {
            fclose(fin);
            fclose(fout);
            return;
        }

        heaps.assign(num_heaps + 1, nullptr);

        for (int i = 0; i < num_ops; ++i) {
            int op;
            fscanf(fin, "%d", &op);

            if (op == 1) {
                int m, x;
                fscanf(fin, "%d %d", &m, &x);
                Node* newNode = new Node(x);
                heaps[m] = merge(heaps[m], newNode);
            }
            else if (op == 2) {
                int m;
                fscanf(fin, "%d", &m);
                if (heaps[m]) {
                    fprintf(fout, "%d\n", heaps[m]->value);
                    Node* oldRoot = heaps[m];
                    heaps[m] = combineSiblings(oldRoot->child);
                    delete oldRoot;
                }
            }
            else if (op == 3) {
                int m1, m2;
                fscanf(fin, "%d %d", &m1, &m2);
                if (m1 != m2 && heaps[m2]) {
                    heaps[m1] = merge(heaps[m1], heaps[m2]);
                    heaps[m2] = nullptr;
                }
            }
        }

        fclose(fin);
        fclose(fout);
    }
};

int main() {
    // Matches the Python file_prefix logic
    MergeHeapProblem problem("mergeheap");
    problem.solve();
    return 0;
}