#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* child;
    Node* sibling;

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

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->val < b->val) swap(a, b);

    b->sibling = a->child;
    a->child = b;
    return a;
}

Node* mergePairs(Node* node) {
    if (!node || !node->sibling) return node;

    Node* a = node;
    Node* b = node->sibling;
    Node* rest = b->sibling;

    a->sibling = b->sibling = nullptr;
    return merge(merge(a, b), mergePairs(rest));
}

Node* pop(Node* root) {
    return mergePairs(root->child);
}

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

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

    vector<Node*> heap(N + 1, nullptr);

    for (int i = 0; i < Q; ++i) {
        int op;
        fin >> op;
        if (op == 1) {
            int m, x;
            fin >> m >> x;
            heap[m] = merge(heap[m], new Node(x));
        } else if (op == 2) {
            int m;
            fin >> m;
            fout << heap[m]->val << '\n';
            heap[m] = pop(heap[m]);
        }
        else if (op == 3) {
            int a, b;
            fin >> a >> b;
            if (a == b) continue;
            heap[a] = merge(heap[a], heap[b]);
            heap[b] = nullptr;
        }

    }

    fin.close();
    fout.close();
    return 0;
}