#include<bits/stdc++.h>

using namespace std;

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

class Nod {
    private:

        int valoare;
        Nod* copilStang;
        Nod* frateDrept;

    public:

        Nod(int val = 0, Nod* copil = NULL, Nod* frate = NULL):valoare(val),copilStang(copil),frateDrept(frate){}

        void setValoare(int v);
        void setCopilStang(Nod* copil);
        void setFrateDrept(Nod* frate);

        int getValoare();
        Nod* getCopilStang();
        Nod* getFrateDrept();

};

void Nod::setValoare(int v){
    this->valoare = v;
}
void Nod::setCopilStang(Nod* copil){
    this->copilStang = copil;
}
void Nod::setFrateDrept(Nod* frate){
    this->frateDrept = frate;
}
int Nod::getValoare(){
    return this->valoare;
}
Nod* Nod::getCopilStang(){
    return this->copilStang;
}
Nod* Nod::getFrateDrept(){
    return this->frateDrept;
}


class PairingHeap {
    private:

        Nod* radacina;

    public:

        PairingHeap();
        PairingHeap(int x);
        void setRadacina(Nod* rad);
        Nod* getRadacina();

        bool isEmpty();
        void mergeHeaps(PairingHeap heap);
        void insertInHeap(int val);
        void heapify(vector<int> elemente);
        void twoPassMerge();
        void deleteMax();

};

PairingHeap::PairingHeap(){
    this->radacina = NULL;
}
PairingHeap::PairingHeap(int x){
    Nod* aux = new Nod(x);
    this->radacina = aux;
}
void PairingHeap::setRadacina(Nod* rad){
    this->radacina = rad;
}
Nod* PairingHeap::getRadacina(){
    return this->radacina;
}
bool PairingHeap::isEmpty(){
    if(this->radacina == NULL)
        return 1;
    return 0;
}
void PairingHeap::mergeHeaps(PairingHeap heap){

    if (heap.isEmpty()) {
        return;
    }

    if (this->isEmpty()) {

        radacina = heap.radacina;
        return;
    }


    if (this->radacina->getValoare() >= heap.radacina->getValoare()) {
        heap.radacina->setFrateDrept(this->radacina->getCopilStang());            // Adaugam heap la lista de subheapuri
        this->radacina->setCopilStang(heap.radacina);

    }
    else {
        this->radacina->setFrateDrept(heap.radacina->getCopilStang());            // Intai adaugam la heap obiectul curent in lista de subheapuri ale lui heap
        heap.radacina->setCopilStang(this->radacina);
        this->radacina = heap.radacina;

    }


}
void PairingHeap::insertInHeap(int val){
    PairingHeap auxheap = PairingHeap(val);
    this->mergeHeaps(auxheap);

}
void PairingHeap::heapify(vector<int> elemente){

    if (elemente.size()) {
        Nod* n = new Nod(elemente[0]);
        this->radacina = n;

        for (int i = 1; i < elemente.size(); i++) {
            this->insertInHeap(elemente[i]);
        }
    }
}
void PairingHeap::twoPassMerge(){

    if (radacina->getCopilStang() == NULL){
        radacina = NULL;
        return;
    }

    if (radacina->getCopilStang()->getFrateDrept() == NULL){
        radacina = radacina->getCopilStang();
        return;
    }

    vector<PairingHeap> aux;
    int nr = 0;

    Nod* curent = this->radacina->getCopilStang();
    Nod* frateCurent = this->radacina->getCopilStang()->getFrateDrept();
    Nod* frateUrmator = frateCurent->getFrateDrept();

    do {

        aux.push_back(PairingHeap());
        PairingHeap frateDreptHeap = PairingHeap();

        aux[nr].setRadacina(curent);
        frateDreptHeap.radacina = frateCurent;

        aux[nr].mergeHeaps(frateDreptHeap);

        if (frateUrmator == NULL){
            nr++;
            break;
        }

        curent = frateUrmator;

        if(curent->getFrateDrept() == NULL) {
            nr++;

            aux.push_back(PairingHeap());
            aux[nr].radacina = curent;

            nr++;
            break;
        }

        frateCurent = curent->getFrateDrept();
        frateUrmator = frateCurent->getFrateDrept();

        nr++;

    } while (curent != NULL);


    this->radacina = aux[nr - 1].radacina;

    for (int i = nr - 2; i >= 0; i--) {

        this->mergeHeaps(aux[i]);

    }

}
void PairingHeap::deleteMax(){
    if (!this->isEmpty()){
        this->twoPassMerge();
    }
}


int main() {

    int N,Q;
    vector<PairingHeap> heapuri;
    fin>>N>>Q;

    int op,x,y;

    for(int i = 0; i <= N ;i++)
        heapuri.push_back(PairingHeap());

    for(int i = 0; i < Q; i++)
    {
        fin>>op;

        switch(op){

        case 1:{
            fin>>x>>y;
            heapuri[x].insertInHeap(y);
            break;
        }

        case 2:{
            fin>>x;
            fout<<heapuri[x].getRadacina()->getValoare()<<"\n";
            heapuri[x].deleteMax();
            break;
        }

        case 3:{
            fin>>x>>y;
            heapuri[x].mergeHeaps(heapuri[y]);

        }

        }

    }

    return 0;
}