#include<bits/stdc++.h>

using namespace std;

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

class Nod {
    public:
        int valoare;
        Nod* copilStang;
        Nod* frateDrept;

        Nod();
        Nod(int val);
        Nod(int val, Nod* copil, Nod* frate);


};

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


class PairingHeap {

    public:
        Nod* radacina;



        PairingHeap();
        PairingHeap(int x);


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

};

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

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

    if (this->isEmpty()) {
        this->radacina = heap.radacina;
        return;
    }


    if (this->radacina->valoare >= heap.radacina->valoare) {
        heap.radacina->frateDrept = this->radacina->copilStang;
        this->radacina->copilStang = heap.radacina;

    }
    else {
        this->radacina->frateDrept = heap.radacina->copilStang;
        heap.radacina->copilStang = this->radacina;
        this->radacina = heap.radacina;

    }


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

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

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

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

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

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

    vector<PairingHeap> aux;
    int nr = 0;

    Nod* curent = this->radacina->copilStang;
    Nod* frateCurent = this->radacina->copilStang->frateDrept;
    Nod* frateUrmator = frateCurent->frateDrept;

    do {

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

        aux[nr].radacina = curent;
        frateDreptHeap.radacina = frateCurent;

        aux[nr].mergeHeaps(frateDreptHeap);

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

        curent = frateUrmator;

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

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

            nr++;
            break;
        }

        frateCurent = curent->frateDrept;
        frateUrmator = frateCurent->frateDrept;

        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 N,Q;
    vector<PairingHeap> heapuri;


    int op,x,y;

int main() {

    fin>>N>>Q;

    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].maxim()<<"\n";
            heapuri[x].deleteMax();
            break;
        }

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

        }

        }

    }

    return 0;
}