#include <fstream>
using namespace std;
ifstream f("mergeheap.in");
ofstream g("mergeheap.out");

class Node
{
private:
    int val;
    Node *child;
    Node *bro;
public:
    Node(int valoare):val(valoare),child(nullptr),bro(nullptr){}
    Node(Node* nod)
    {
        val=nod->val;
        child=nod->child;
        bro=nod->bro;
    }
    int getData() const
    {
        return val;
    }
    Node *getChild() const {
        return child;
    }

    void setChild(Node *child) {
        Node::child = child;
    }

    Node *getBro() const {
        return bro;
    }

    void setBro(Node *bro) {
        Node::bro = bro;
    }
};
class PairingHeap
{
private:
    Node* radacina;
public:
    PairingHeap() : radacina(nullptr) {}
    //pentru cerinta 1
    void insert(const int& value)
    {
        if(radacina==nullptr)
        {
            radacina = new Node(value);
            return;
        }
        Node* aux = new Node(value);
        if(radacina->getData() < value)
            swap(radacina, aux);
        aux->setBro(radacina->getChild());
        radacina->setChild(aux);
    }
    //cerinta 2
    int getMaxim()
    {
        int maxim = radacina->getData();
        Node* oldroot = radacina;
        if(radacina->getChild()== nullptr)
            radacina = nullptr;
        else radacina = mergePairs(radacina->getChild());
        delete oldroot;
        return maxim;
    }
    //cerinta 3
    void merge(PairingHeap& other)
    {
        if(other.radacina == nullptr)return;
        if(radacina == nullptr){
            swap(radacina,other.radacina);
            return;
        }
        if(other.radacina->getData()>radacina->getData()){
            swap(radacina,other.radacina);
        }
        other.radacina->setBro(radacina->getChild());
        radacina->setChild(other.radacina);
        other.radacina = nullptr;
    }
    //cerinta 2
    Node* mergePairs(Node* first) {
    if (first == nullptr || first->getBro() == nullptr) {
        // cazurile de baza: daca nu avem cel putin doua noduri, sau
        // daca avem doar un nod si nu avem nimic de facut, returnam nodul curent
        return first;
    }

    // preluam cele doua noduri si le sortam in functie de valoare
    Node* left = first;
    Node* right = first->getBro();
    if (left->getData() > right->getData()) {
        left = first->getBro();
        right = first;
    }

    // legam copiii celui mai mic nod la fratele mai mare
    if (right->getChild() == nullptr) {
        right->setChild(left);
    } else {
        Node* curr = right->getChild();
        while (curr->getBro() != nullptr) {
            curr = curr->getBro();
        }
        curr->setBro(left);
    }

    // apelam recursiv functia pe urmatoarea pereche de noduri si unificam rezultatul
    Node* next = right->getBro();
    Node* merged = mergePairs(next);
    right->setBro(merged);

    // returnam radacina heap-ului
    return right;
}


};

int main()
{
    int N, Q;
    f >> N >> Q;
    PairingHeap *heap = new PairingHeap[N];
    for (int i = 0; i < Q; i++)
    {
        int op, m, x, y;
        f >> op;
        switch (op)
        {
            case 1:
                f >> m >> x;
                heap[m-1].insert(x);
                break;

            case 2:
                f >> m;
                g << heap[m-1].getMaxim()<<"\n";
                break;

            case 3:
                f >> x >> y;
                heap[x-1].merge(heap[y-1]);
                break;
        }
    }
    delete[] heap;
    return 0;
}