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

    Heap b(this->radacina->copil);
    this->radacina->copil = NULL;

    while (b.radacina != NULL) {
        Heap temp(b.radacina);
        b.radacina = b.radacina->frate;
        temp.radacina->frate = NULL;
        this->reuniune(temp);
    }

    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]);
        }
        cout<<i+1<<" ";
    }
//    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;
}