#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <ctime>

struct TreapNode {
    int key, priority;
    TreapNode *left, *right;

    TreapNode(int key) : key(key), priority(rand()), left(nullptr), right(nullptr) {}
};

class Treap {
private:
    TreapNode* root;

    TreapNode* rightRotate(TreapNode* y) {
        TreapNode* x = y->left;
        y->left = x->right;
        x->right = y;
        return x;
    }

    TreapNode* leftRotate(TreapNode* x) {
        TreapNode* y = x->right;
        x->right = y->left;
        y->left = x;
        return y;
    }

    TreapNode* _insert(TreapNode* node, int key) {
        if (!node) return new TreapNode(key);
        if (key <= node->key) {
            node->left = _insert(node->left, key);
            if (node->left->priority > node->priority)
                node = rightRotate(node);
        } else {
            node->right = _insert(node->right, key);
            if (node->right->priority > node->priority)
                node = leftRotate(node);
        }
        return node;
    }

    TreapNode* _deleteNode(TreapNode* node, int key) {
        if (!node) return node;
        if (key == node->key) {
            if (!node->left || !node->right) {
                TreapNode* temp = node->left ? node->left : node->right;
                delete node;
                node = temp;
            } else {
                if (node->left->priority < node->right->priority) {
                    node = leftRotate(node);
                    node->left = _deleteNode(node->left, key);
                } else {
                    node = rightRotate(node);
                    node->right = _deleteNode(node->right, key);
                }
            }
        } else if (key < node->key) {
            node->left = _deleteNode(node->left, key);
        } else {
            node->right = _deleteNode(node->right, key);
        }
        return node;
    }

public:
    Treap() : root(nullptr) {}

    void insert(int key) {
        root = _insert(root, key);
    }

    int getMaxAndRemove() {
        TreapNode* node = root;
        TreapNode* parent = nullptr;
        while (node && node->right) {
            parent = node;
            node = node->right;
        }
        if (!node) return -1; // Treap is empty

        int maxValue = node->key;
        if (parent) {
            parent->right = _deleteNode(node, maxValue);
        } else {
            root = _deleteNode(root, maxValue);
        }
        return maxValue;
    }

    void merge(Treap &other) {
        _mergeHelper(other.root);
        other.root = nullptr; // The other treap is now empty
    }

    void _mergeHelper(TreapNode* node) {
        if (!node) return;
        insert(node->key);
        _mergeHelper(node->left);
        _mergeHelper(node->right);
    }
};

int main() {
    srand(time(NULL)); // Initialize random seed for priorities

    std::ifstream infile("mergeheap.in");
    std::ofstream outfile("mergeheap.out");
    int N, Q;
    infile >> N >> Q;
    std::vector<Treap> treaps(N+1);

    for (int i = 0; i < Q; i++) {
        int type, a, b;
        infile >> type;
        switch (type) {
            case 1:
                infile >> a >> b;
                treaps[a].insert(b);
                break;
            case 2:
                infile >> a;
                outfile << treaps[a].getMaxAndRemove() << std::endl;
                break;
            case 3:
                infile >> a >> b;
                treaps[a].merge(treaps[b]);
                break;
        }
    }

    return 0;
}