#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(){}
};

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;
    }
    h.radacina = NULL;
}


int Heap::stergere_max()
{
    int maxim = this->radacina->valoare;

    if (this->radacina->copil == NULL) {
        delete this->radacina;
        this->radacina = NULL;
    }
    else {
        vector<Heap> subheaps;
        Nod* nod_curent = this->radacina->copil;

        while (nod_curent != NULL) {
            Nod* next_nod = nod_curent->frate;
            nod_curent->frate = NULL;
            subheaps.push_back(Heap(nod_curent));
            nod_curent = next_nod;
        }

        this->radacina = subheaps[0].radacina;
        for (int i = 1; i < subheaps.size(); i++)
            this->reuniune(subheaps[i]);
    }

    return maxim;
}

int main()
{
    Heap h[101];
    int n, q;
    f>>n>>q;
    for(int i=0; i<q; i++){
        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<<" ";
    }

    return 0;
}