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

ifstream fileIn("mergeheap.in");
ofstream fileOut("mergeheap.out");

class Heapp;
class Nde {
private:
    Nde* before;
    Nde* after;
    Nde* child;
    Nde* parent;
    int value;
    int degree;
public:
    int getValue(){return value;}
    static Nde* merge(Nde* nde,Nde* otherNde);
    friend class Heapp;
    static void addChild(Nde* p, Nde* c);
};

Nde* Nde::merge(Nde* nde,Nde* otherNde) {
    if(nde == nullptr) return otherNde;
    if(otherNde == nullptr)  return nde;
    if(nde->getValue() <  otherNde->getValue()) { //interschimba
        Nde* temporary = nde;
        nde = otherNde;
        otherNde = temporary;
    }
    Nde* afterNde = node->after;
    Nde* beforeONde = otherNde->before;
    node->after = otherNde;
    otherNde->before = nde;
    afterNde-> before = beforeONde;
    beforeONde-> after = afterNde;

    return node;
}

void Nde::addChild(Nde* parent, Nde* child) {
        child ->before = child->after = child;
        child->parent = parent;
        parent->degree++;
        parent->child = Nde::merge(parent->child, child);
}

class Heapp {
public:
    Nde* maxHeapp;
    Heapp();
    void insert(int x);
    void unionH(Heapp& otherH);
    int getMax(){return maxHeapp->getValue();};
    void removeMax();
    Nde* removeFromList(Nde* nde);
    Nde* cleanup();
    void unparent(Nde* nde);
};
    Heapp::Heapp() {
        this->maxHeapp = nullptr;
    }

Nde* Heapp::cleanup() {
    Nde* node = maxHeapp;
    Nde* degrees[70] ={nullptr};
    while(true) {
        if(degrees[nde->degree]!= nullptr) {
            Nde* t = degrees [nde->degree];
            if(t==nde) {
                break;
            }
            degrees[nde->degree] = nullptr;
            if(nde->value > t->value) {
                t->before->after = t->after;
                t->after-> before = t->before;
                Nde::addChild(nde,t);
            } else  {
                t->before->after = t->after;
                t->after->before = t->before;
                if(nde->after == node) {
                    t-> after = t->before = t;
                    Nde::addChild(t,nde);
                    nde=t;
                } else {
                    nde->before -> after = t;
                    nde->after->before= t;
                    t->before= nde->before;
                    t->after = nde->after;
                    Nde::addChild(t, nde);
                    nde=t;
                }

            }
            continue;
        }else {
        degrees[nde->degree] = nde;
        }
        nde=nde->after;
    }
    Nde* maxH = nde;
    Nde* start = nde;
    do {
        if(nde->value > maxH->value) {
            maxH = nde;
        }
        nde= nde->after;
    }
    while (nde != start );
    return maxH;
}

void Heapp::unparent(Nde* nde) {
    if(nde== nullptr) {
        return;
    }
    Nde* copyN = nde;
    do {
        copyN->parent = nullptr;
        copyN = copyN->after;
    } while (copyN != node);
}

Nde* Heapp::removeFromList(Nde* nde) {
    if(nde->after == nde){ //
        nde = nde->child;
        return nde;;
    }
    nde->after->before = nde->before;
    nde->before->after = nde->after;
    nde = Nde::merge(nde->after, nde->child);
    return nde;
}

void Heapp::removeMax() {
    if(this->maxHeapp == nullptr) {
        return;
    }
    unparent(maxHeapp->child);
    maxHeapp= removeFromList(maxHeapp);
    if(maxHeapp != nullptr) {
        maxHeapp = cleanup();
    }
}

void Heapp::insert(int x) {
    Nde* p = new Nde;
    p-> value = x;
    p-> before = p->after = p;
    p->degree = 0;
    p ->parent = p->child = nullptr;
    maxHeapp = Nde::merge(maxHeapp,p);
}

void Heapp::unionH(Heapp& otherH) {
    this->maxHeapp = Nde::merge(maxHeapp, otherH.maxHeapp);
    otherH.maxHeapp = nullptr;
}

Heapp* heaps[101] = {nullptr};
int main()
{   int n, q, op, m, x, a,b;
    fileIn >> n >> q;

    for(int i = 0; i < q ; i++) {
        fileIn >> op;
        switch (op) {
        case 1:
            fileIn >> m >> x;
            if(heaps[m] == nullptr) {
                heaps[m] = new Heapp();
                heaps[m] ->insert(x);
            }
            else {
                heaps[m]->insert(x);
            }
            break;
        case 2:
            fileIn >> m;
            fileOut << heaps[m]->getMax() <<'\n';
            heaps[m] ->removeMax();
            break;

        case 3:
            fileIn >>a>> b;
            heaps[a]->unionH(*heaps[b]);
            break;
            }
    }
    return 0;
}