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

using namespace std;

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

class Nod
{
public:
    int valoare;
    Nod* copil;
    Nod* frate;
    Nod* stanga;
    Nod* dreapta;
    int rankNod;

    Nod(int valoare){
        this->valoare = valoare;
        this->copil = NULL;
        this->frate = NULL;
        this->stanga = NULL;
        this->dreapta = NULL;
        this->rankNod = 0;
    }

//    ~Nod()
//    {
//        if(copil != NULL){
//            delete copil;
//            copil = NULL;
//        }
//        if(frate != NULL){
//            delete frate;
//            frate = NULL;
//        }
//        if(stanga != NULL){
//            delete stanga;
//            stanga = NULL;
//        }
//        if(dreapta != NULL){
//            delete dreapta;
//            dreapta = NULL;
//        }
//    }
};

class RankPairingHeap
{
public:
    Nod* maxim;

    RankPairingHeap(){this->maxim = NULL;}
    RankPairingHeap(Nod* a){this->maxim = a;}

    void inserare(int x);
    void reuniune(RankPairingHeap& h);
    int stergere_max();
    void mergeNode(Nod* &a, Nod* &b);
};

void RankPairingHeap :: inserare(int x)
{
    if(this->maxim == NULL){
        this->maxim = new Nod(x);}
    else{
        Nod* a = new Nod(x);
        if(this->maxim->valoare > x){
            a->stanga = this->maxim;
            if(this->maxim->dreapta != NULL) {
                a->dreapta = this->maxim->dreapta;
                this->maxim->dreapta->stanga = a;}
            this->maxim->dreapta = a;

        }
        else{
            a->dreapta = this->maxim;
            this->maxim = a;
        }
    }
}

void RankPairingHeap :: reuniune(RankPairingHeap& h)
{
    if(h.maxim == NULL)
        return;
    if(this->maxim == NULL){
        this->maxim = h.maxim;
        h.maxim = NULL;
        return;
    }
    if(this->maxim->valoare > h.maxim->valoare){
        Nod* aux = this->maxim;
        while(aux->dreapta != NULL)
            aux = aux->dreapta;
        aux->dreapta = h.maxim;
        h.maxim->stanga = aux;
    }
    else{
        Nod* aux = h.maxim;
        while(aux->dreapta != NULL)
            aux = aux->dreapta;
        aux->dreapta = this->maxim;
        this->maxim->stanga = aux;
        this->maxim = h.maxim;
    }
    h.maxim = NULL;
}

int RankPairingHeap::stergere_max()
{

    int m = this->maxim->valoare;
    if (this->maxim->dreapta == NULL && this->maxim->rankNod == 0) {
        this->maxim = NULL;
        return m;
    }

    Nod* a = this->maxim->copil;
    while (a != NULL) {
        this->inserare(a->valoare);
        this->maxim->dreapta->copil = a->copil;
       // RankPairingHeap aux(a);
       // this->reuniune(aux);
        a = a->frate;
    }

    this->maxim = this->maxim->dreapta;


    Nod* z = this->maxim->dreapta;
    Nod* nod_max = this->maxim;
    while (z != NULL) {
        if (z->valoare > nod_max->valoare) {
            nod_max = z;
        }
        z = z->dreapta;
    }
    if (nod_max != this->maxim) {
        nod_max->stanga->dreapta = nod_max->dreapta;
        if (nod_max->dreapta != NULL)
            nod_max->dreapta->stanga = nod_max->stanga;
        nod_max->stanga = NULL;
        nod_max->dreapta = this->maxim;
        this->maxim = nod_max;
    }

    Nod* x = this->maxim;
//    while (x != NULL) {
//        Nod* y = x->dreapta;
//        if (y != NULL && x->rankNod == y->rankNod) {
//            mergeNode(x, y);
//            x->rankNod = x->copil->rankNod + 1;
//            x->dreapta = y->dreapta;
//            if (y->dreapta != NULL) {
//                y->dreapta->stanga = x;
//            }
//            y->dreapta = NULL;
//        }
//        x = x->dreapta;
//    }

    return m;
}

void RankPairingHeap :: mergeNode(Nod* &a, Nod* &b)
{
    if(a->valoare > b->valoare){
        b->frate = a->copil;
        a->copil = b;
    }
    else{
        a->frate = b->copil;
        b->copil = a;
        a = b;
    }
}

int main()
{
    RankPairingHeap 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<<" ";
    }

//    RankPairingHeap a, b;
//    a.inserare(1);
//    a.inserare(2);
//    a.inserare(3);
//    a.inserare(4);
//    a.inserare(5);
//    a.inserare(10);
//    b.inserare(7);
//    b.inserare(16);
//    b.inserare(8);
//    a.reuniune(b);
//    cout<<a.stergere_max()<<endl;
//    cout<<a.stergere_max();
//    Nod* x = a.maxim;
//    while(x != NULL){
//        cout<<x->valoare<<"="<<x->rankNod<<" ";//<<x->copil->valoare<<"="<<x->copil->rankNod<<" ";
//        x = x->dreapta;
//    }
 //   cout<<x->dreapta->dreapta->copil->valoare;
    //cout<<a.radacina->valoare;

    return 0;
}