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

using namespace std;

struct PairingHeapNode {
    int key;
    PairingHeapNode* child;
    PairingHeapNode* next;
};

PairingHeapNode* newPairingHeapNode(int key) {
    PairingHeapNode* node = new PairingHeapNode;
    node->key = key;
    node->child = node->next = nullptr;
    return node;
}

PairingHeapNode* mergePairs(PairingHeapNode* first);

PairingHeapNode* mergePairingHeaps(PairingHeapNode* a, PairingHeapNode* b) {
    if (!a)
        return b;
    if (!b)
        return a;
    if (a->key < b->key)
        swap(a, b);
    b->next = a->child;
    a->child = b;
    return a;
}

PairingHeapNode* mergePairs(PairingHeapNode* first) {
    if (!first || !first->next) {
        return first;
    }
    PairingHeapNode *a = first, *b = first->next, *c = first->next->next;
    a->next = nullptr;
    b->next = nullptr;
    return mergePairingHeaps(mergePairingHeaps(a, b), mergePairs(c));
}

PairingHeapNode* removeMax(PairingHeapNode* heap) {
    if (!heap)
        return nullptr;
    PairingHeapNode* maxChild = heap->child;
    delete heap;
    return mergePairs(maxChild);
}

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

    int N, Q, op, a, b;
    in >> N >> Q;

    vector<PairingHeapNode*> heaps(N + 1, nullptr);

    while (Q--) {
        in >> op;
        if (op == 1) {
            in >> a >> b;
            heaps[a] = mergePairingHeaps(heaps[a], newPairingHeapNode(b));
        } else if (op == 2) {
            in >> a;
            out << heaps[a]->key << endl;
            heaps[a] = removeMax(heaps[a]);
        } else if (op == 3) {
            in >> a >> b;
            heaps[a] = mergePairingHeaps(heaps[a], heaps[b]);
            heaps[b] = nullptr;
        }
    }

    in.close();
    out.close();
    return 0;
}