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

using namespace std;

ifstream f("mergeheap.in");
ofstream g("mergeheap.out");

class Nod
{
public:
    int valoare;
    Nod* copil;
    Nod* frate;

    Nod(int valoare){
        this->valoare = valoare;
        this->copil = NULL;
        this->frate = NULL;
    }

//    ~Nod()
//    {
//        if(this->copil != NULL){
//            delete[] this->copil;
//            this->copil = NULL;
//        }
//        if(this->frate != NULL){
//            delete[] this->frate;
//            this->frate = NULL;
//        }
//    }
};

class Heap
{
public:
    Nod* radacina;

    Heap(){this->radacina = NULL;}
    Heap(Nod* radacina){this->radacina = radacina;}

    void inserare(int x);
    void reuniune(Heap& h);
    int stergere_max();

//    ~Heap()
//    {
//        if(this->radacina != NULL){
//            delete[] this->radacina;
//            this->radacina = NULL;
//        }
//    }
};

void Heap :: inserare(int x)
{
        if(this->radacina == NULL)
            this->radacina = new Nod(x);

        else{
            Heap b;
            b.inserare(x);
            if(this->radacina->valoare > x){
                b.radacina->frate = this->radacina->copil;
                this->radacina->copil = b.radacina;
            }
            else{
                b.radacina->copil = this->radacina;
                this->radacina =  b.radacina;
            }
        }
    }

void Heap :: reuniune(Heap& h)
{
    if(this->radacina == NULL)
        *this = h;
    else if(this->radacina->valoare > h.radacina->valoare){
        h.radacina->frate = this->radacina->copil;
        this->radacina->copil = h.radacina;
    }
    else{
        this->radacina->frate = h.radacina->copil;
        h.radacina->copil = this->radacina;
        *this = h;
    }
}

int Heap :: stergere_max()
{
    int maxim = this->radacina->valoare;
    this->radacina = this->radacina->copil;
    Heap b(this->radacina->frate);
    while(b.radacina != NULL){
        Nod* n = new Nod(b.radacina->valoare);
        Heap aux(n);
        this->reuniune(aux);
        b.radacina = b.radacina->frate;
        }
    return maxim;
}

int main()
{
    vector<Heap> h;
    int n, q;
    f>>n>>q;
    for(int i=0; i<n; i++){
        Heap aux;
        h.push_back(aux);
    }

    for(int i=0; i<q; i++){
        //cout<<"a"<<endl;
        int j, k, m;
        f>>j;
        if(j == 2){
            f>>k;
            g<<h[k].stergere_max()<<endl;
        }
        else{
            f>>k>>m;
            if(j == 1)
                h[k].inserare(m);
            else h[k].reuniune(h[m]);
        }
    }
//    Heap a, b;
//    a.inserare(3);
//    a.inserare(5);
//    a.inserare(4);
//    b.inserare(1);
//    b.inserare(2);
//    a.reuniune(b);
//    cout<<a.radacina->valoare<<endl<<a.stergere_max()<<endl<<a.radacina->valoare<<endl;
//    a.stergere_max();
//    cout<<a.radacina->valoare;

    return 0;
}