#include <iostream>
#include <list>
#include <algorithm>
#include <fstream>
#include <list>

using namespace std;

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

int n,m,op,a,b;

struct Nod
{
    int val,grad;
    Nod *fiu,*frate,*tata;
};

Nod* New(int val)
{
    Nod *acm = new Nod;
    acm->val = val;
    acm->grad = 0;
    acm->fiu = acm->frate = acm->tata = NULL;
    return acm;
}

Nod* Link(Nod *a, Nod *b)
{
    b->tata = a;
    b->frate = a->fiu;
    a->fiu = b;
    a->grad++;

    return a;
}

list<Nod*> Union(list<Nod*> a,list<Nod*> b)
{
    list<Nod*> nou;
    list<Nod*>::iterator i,j;
    i = a.begin();
    j = b.begin();
    while (i != a.end() && j != b.end())
    {
        if ((*i)->grad <= (*j)->grad)
        {
            nou.push_back(*i);
            i++;
        }
        else
        {
            nou.push_back(*j);
            j++;
        }
    }
    while (i != a.end())
    {
        nou.push_back(*i);
        i++;
    }
    while (j != b.end())
    {
        nou.push_back(*j);
        j++;
    }
    return nou;
}

list<Nod*> Ajustare(list<Nod*> heap)
{
    if (heap.size() <= 1) return heap;

    list<Nod*>::iterator last,x,nxt;
    last = x = nxt = heap.begin();

    if (heap.size() == 2)
    {
        x++;
        nxt = heap.end();
    }
    else
    {
        x++;
        nxt = x;
        nxt++;
    }


    if (m == 4)
    {
        for (auto y:heap) cout << y->grad << " ";
        cout << "\n";
    }
    while (last != heap.end())
    {
        ///if (m == 4 && (*x)->grad == 2 &&  (*last)->grad == 2);
        ///if (m == 4 && (*x)->grad == 2 &&  (*last)->grad == 2) cout << (nxt != heap.end());
        if (x == heap.end() && last != heap.end())
        {
            last++;
        }
        else if ((*last)->grad < (*x)->grad)
        {
            x++;
            last++;
            if (nxt != heap.end()) nxt++;
        }
        else if (nxt != heap.end() && (*last)->grad == (*x)->grad && (*x)->grad == (*nxt)->grad)
        {
            last++;
            x++;
            nxt++;
        }
        else if ((*last)->grad == (*x)->grad)
        {
            if ((*x)->val > (*last)->val) swap(*x,*last);
            *last = Link(*last, *x);
            x = heap.erase(x);
            ///nxt = x;
            if (nxt != heap.end()) nxt++;
        }
    }
    return heap;
}

Nod* Maxi(list<Nod*> heap)
{
    list<Nod*>::iterator it = heap.begin();

    Nod* mi = *it;
    while (it != heap.end())
    {
        if ((*it)->val > mi->val)
        {
            mi = *it;
        }
        it++;
    }
    return mi;
}

list<Nod*> Extrage(Nod* cap)
{
    list<Nod*> nw;
    Nod *tmp = cap->fiu,*nxt;

    while (tmp != NULL)
    {
        nxt = tmp;
        tmp = tmp->frate;
        nxt->frate = NULL;
        nw.push_front(nxt);
    }
   /// reverse(nw.begin(), nw.end());
    return nw;
}

list<Nod*> Sterge_max(list<Nod*> heap)
{
    list<Nod*> nw;
    Nod* maxi = Maxi(heap);
    out << maxi->val << "\n";
    list<Nod*>::iterator it = heap.begin();

    while (it != heap.end())
    {
        if (*it != maxi) nw.push_back(*it);
        it++;
    }
    list<Nod*> lol;
    lol = Extrage(maxi);

    heap = Union(nw, lol);
    heap = Ajustare(heap);
    return heap;

}

list<Nod*> Insert(int val,list<Nod*> heap)
{
    Nod *temp = New(val);
    list<Nod*> nw;
    nw.push_back(temp);
    heap = Union(heap, nw);
    heap = Ajustare(heap);
    return heap;
}

list<Nod*> multimi[105];

int main()
{
    int cnt = 0;
    in >> n >> m;
    while (m--)
    {
        in >> op;
        cnt++;
        if (op == 1)
        {
            in >> a >> b;
            multimi[a] = Insert(b, multimi[a]);
        }
        else if (op == 2)
        {
            in >> a;
            multimi[a] = Sterge_max(multimi[a]);
        }
        else
        {
            in >> a >> b;
            multimi[a] = Union(multimi[a], multimi[b]);

            multimi[a] = Ajustare(multimi[a]);
            multimi[b].clear();
        }

    }
    return 0;
}