#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(copil != NULL){
            delete copil;
            copil = NULL;
        }
        if(frate != NULL){
            delete frate;
            frate = NULL;
        }
    }
};

class Heap
{
public:
    Nod* radacina;

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

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

    ~Heap()
    {
        if(radacina != NULL){
            delete radacina;
            radacina = NULL;
        }
    }
};

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

        else{
            Heap b(x);
            this->reuniune(b);
        }
    }

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;

    Nod* x = this->radacina;
    this->radacina = this->radacina->copil;
    x->copil = NULL;

    Nod* p = x->frate;

    delete x;

    Heap* b = new Heap();
    b->radacina = p;

    while (b->radacina != NULL) {
        Nod* frate = b->radacina->frate;
        b->radacina->frate = NULL;
        Nod* aux = b->radacina;
        Heap* auxHeap = new Heap(aux);
        this->reuniune(*auxHeap);
        b->radacina = frate;
        delete auxHeap;
    }

    delete b;

    return maxim;
}


int main()
{
    Heap h[101];
    int n, q;
    f>>n>>q;

    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;
}