#include <fstream>
#include <vector>
using namespace std;
ifstream f("mergeheap.in");
ofstream g("mergeheap.out");
struct nod{
    int val;
    int grad;
    nod *fiu;
    nod *parinte;
    nod *st;
    nod *dr;
    bool marcat;
};
class heapfibonacci
{
    int noduri;
    nod *maxim;
public:
    heapfibonacci();
    ~heapfibonacci();
    void insereazanod(int nr);
    int extragemaxim();
    void reuniuneheap(heapfibonacci &heap);

    nod *reuniunenoduri(nod *x, nod *y);
    void curata(nod *x);
    void mutacopii(nod *copil);
    nod *izoleazamaxim();
    void consolideaza();
    void adaugacopil(nod *copil, nod *tata);
    void stergedinlista(nod *x);
};
void heapfibonacci::stergedinlista(nod *x)
{
    if (x->dr == x)
        return;
    (x->st)->dr = x->dr;
    (x->dr)->st = x->st;
    x->st = x->dr = x;
}
heapfibonacci::heapfibonacci()
{
    maxim = nullptr;
    noduri = 0;
}
heapfibonacci::~heapfibonacci()
{
    curata(maxim);
}
void heapfibonacci::curata(nod *x)
{
    if(x != nullptr)
    {
        nod *temp = x;
        do
        {
            nod *aux = temp;
            temp = temp->dr;
            curata(aux->fiu);
            delete aux;
        }while(temp != x);
    }
}
void heapfibonacci::insereazanod(int nr)
{
    nod *n = new nod;
    n->val = nr;
    n->grad = 0;
    n->fiu = nullptr;
    n->parinte = nullptr;
    n->st = n;
    n->dr = n;
    n->marcat = false;
    maxim = reuniunenoduri(maxim, n);
    noduri++;
}
nod *heapfibonacci::reuniunenoduri(nod *x, nod *y)
{
    if(x == nullptr)
        return y;
    if(y == nullptr)
        return x;
    if(x->val < y->val)
    {
        nod *temp = x;
        x = y;
        y = temp;
    }
    nod *fost_dreapta_x = x->dr;
    nod *fost_stanga_y = y->st;
    x->dr = y;
    y->st = x;
    fost_dreapta_x->st = fost_stanga_y;
    fost_stanga_y->dr = fost_dreapta_x;
    return x;
}
void heapfibonacci::reuniuneheap(heapfibonacci &heap)
{
    maxim = reuniunenoduri(maxim, heap.maxim);
    noduri += heap.noduri;
    heap.maxim = nullptr;
    heap.noduri = 0;
}
void heapfibonacci::mutacopii(nod *copil)
{
    if(copil == nullptr)
        return;
    nod *temp = copil;
    do
    {
        temp->parinte = nullptr;
        temp = temp->dr;
    }while(copil != temp);
}
int heapfibonacci::extragemaxim()
{
    nod *maxsters = izoleazamaxim();
    int valoare = maxsters->val;
    delete maxsters;
    return valoare;
}
nod *heapfibonacci::izoleazamaxim()
{
    nod *maxim_curr = maxim;
    if(maxim_curr == nullptr)
    {
        return nullptr;
    }
    mutacopii(maxim_curr->fiu);
    reuniunenoduri(maxim_curr, maxim_curr->fiu);
    if(maxim_curr == maxim_curr->dr)
    {
        maxim = nullptr;
    }else
    {
        maxim = maxim_curr->dr;
    }

    stergedinlista(maxim_curr);
    if(maxim != nullptr)
    {
        consolideaza();
    }
    noduri--;
    return maxim_curr;
}
void heapfibonacci::adaugacopil(nod *copil, nod *tata)
{
    copil->parinte = tata;
    tata->fiu = reuniunenoduri(tata->fiu, copil);
    tata->grad++;
    copil->marcat = false;
}
void heapfibonacci::consolideaza()
{
    int copie = noduri;
    int casute = 0;
    while(copie > 0)
    {
        copie >>= 1;
        casute++;
    }
    nod *duble[casute];
    for(int i = 0; i <= casute; i++)
    {
        duble[i] = nullptr;
    }
    vector<nod*> radacini;
    nod *node = maxim;

    do
    {
        radacini.push_back(node);
        node = node->dr;
    } while (node != maxim);


    for (nod *curent : radacini)
    {
        int grd = curent->grad;
        stergedinlista(curent);

        while(duble[grd] != nullptr)
        {
            if (curent->val < duble[grd]->val)
            {
                nod *temp = curent;
                curent = duble[grd];
                duble[grd] = temp;
            }
            adaugacopil(duble[grd], curent);
            duble[grd] = nullptr;
            grd++;
        }

        duble[grd] = curent;
        maxim = curent;
    }



    for (int i = 0; i <= casute; i++)
    {
        if (duble[i] != nullptr && duble[i] != maxim)
        {
            reuniunenoduri(maxim, duble[i]);
        }
    }


    nod* primul = maxim;
    nod* curent = maxim;
    do{
        if (curent->val > maxim->val)
        {
            maxim = curent;
        }
        curent = curent->dr;
    } while (curent != primul);
}
int main()
{
    int n, m, instr, heap, element;
    f >> n >> m;
    heapfibonacci heapuri[n+1];
    for(int i = 0; i < m; i++)
    {
        f >> instr;
        if(instr == 1)
        {
            f >> heap >> element;
            heapuri[heap].insereazanod(element);
        }
        if(instr == 2)
        {
            f >> heap;
            g << heapuri[heap].extragemaxim() << "\n";
        }
        if(instr == 3)
        {
            f >> heap >> element;
            heapuri[heap].reuniuneheap(heapuri[element]);
        }
    }
    return 0;
}