#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

ifstream infile("mergeheap.in");
ofstream outfile("mergeheap.out");

class MergeHeap {
public:
    void insert(int heap_id, int value) {
        heaps[heap_id].push(value);
    }

    int extract_max(int heap_id) {
        if (heaps[heap_id].empty()) return -1;
        int max_val = heaps[heap_id].top();
        heaps[heap_id].pop();
        return max_val;
    }

    void merge(int heap_id1, int heap_id2) {
        if (heap_id1 == heap_id2) return;
        priority_queue<int> &heap1 = heaps[heap_id1];
        priority_queue<int> &heap2 = heaps[heap_id2];

        if (heap1.size() < heap2.size()) {
            swap(heap1, heap2);
            swap(heap_id1, heap_id2);
        }

        while (!heap2.empty()) {
            heap1.push(heap2.top());
            heap2.pop();
        }
    }

private:
    unordered_map<int, priority_queue<int>> heaps;
};

int main() {
    int N, Q;
    infile >> N >> Q;

    MergeHeap merge_heap;

    for (int i = 0; i < Q; ++i) {
        int op_type;
        infile >> op_type;

        if (op_type == 1) {
            int m, x;
            infile >> m >> x;
            merge_heap.insert(m, x);
        } else if (op_type == 2) {
            int m;
            infile >> m;
            int max_val = merge_heap.extract_max(m);
            outfile << max_val << "\n";
        } else if (op_type == 3) {
            int a, b;
            infile >> a >> b;
            merge_heap.merge(a, b);
        }
    }

    infile.close();
    outfile.close();
    return 0;
}