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

using namespace std;

struct Node {
    int key, priority;
    Node *left, *right;
    Node(int key) : key(key), priority(rand()), left(nullptr), right(nullptr) {}
};

class Treap {
private:
    Node* root = nullptr;

    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        y->left = x;
        return y;
    }

    Node* rotateRight(Node* y) {
        Node* x = y->left;
        y->left = x->right;
        x->right = y;
        return x;
    }

    Node* insert(Node* node, int key) {
        if (!node) return new Node(key);
        if (key > node->key) {
            node->right = insert(node->right, key);
            if (node->right->priority > node->priority)
                node = rotateLeft(node);
        } else {
            node->left = insert(node->left, key);
            if (node->left->priority > node->priority)
                node = rotateRight(node);
        }
        return node;
    }

    Node* merge(Node* left, Node* right) {
        if (!left) return right;
        if (!right) return left;
        if (left->priority > right->priority) {
            left->right = merge(left->right, right);
            return left;
        } else {
            right->left = merge(left, right->left);
            return right;
        }
    }

    Node* removeMax(Node* node) {
        if (!node->right) {
            Node* left = node->left;
            delete node;
            return left;
        }
        node->right = removeMax(node->right);
        return node;
    }

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

    int removeMax() {
        assert(root != nullptr); // Guarantee that we do not call this on an empty treap
        Node* node = root;
        while (node->right) node = node->right;
        int maxKey = node->key;
        root = removeMax(root);
        return maxKey;
    }

    void merge(Treap& other) {
        root = merge(root, other.root);
        other.root = nullptr; // Make sure the other treap is empty after merge
    }
};

int main() {
    ifstream fin("mergeheap.in");
    ofstream fout("mergeheap.out");

    int N, Q;
    fin >> N >> Q;

    vector<Treap> treaps(N + 1); // +1 to use 1-based index

    for (int i = 0; i < Q; ++i) {
        int type;
        fin >> type;
        if (type == 1) {
            int m, x;
            fin >> m >> x;
            treaps[m].insert(x);
        } else if (type == 2) {
            int m;
            fin >> m;
            fout << treaps[m].removeMax() << "\n";
        } else if (type == 3) {
            int a, b;
            fin >> a >> b;
            treaps[a].merge(treaps[b]);
        }
    }

    fin.close();
    fout.close();

    return 0;
}