#include <fstream>
#include <vector>
using namespace std;
ifstream f("mergeheap.in");
ofstream g("mergeheap.out");
struct heap
{
    int val;
    vector <heap*> subheap;
};
heap *rad[300011];
void heap_insert(int x,heap *k)
{
    if(rad[x]==0)
    {
        rad[x]=k;
        return;
    }
    if(k->val>rad[x]->val)
    {
        k->subheap.push_back(rad[x]);
        rad[x]=k;
        return;
    }
    rad[x]->subheap.push_back(k);
}
void heap_merge(heap *x,heap *y)
{
    if(x->val<y->val)
        swap(x,y);
    x->subheap.push_back(y);
}
void heap_extract(int x)
{
    if(rad[x]->subheap.size()==0)
    {
        rad[x]=0;
        return;
    }
    heap *k=new heap;
    k=rad[x]->subheap[0];
    int n=rad[x]->subheap.size();
    for(int i=1;i<n;i++)
        heap_merge(k,rad[x]->subheap[i]);
    rad[x]=k;
}
int C,n,m,i,x,y;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>C;
        if(C==1)
        {
            f>>x>>y;
            heap *k=new heap;
            k->val=y;
            if(rad[x]==0)
            {
                rad[x]=k;
                continue;
            }
            if(rad[x]->val>y)
            {
                rad[x]->subheap.push_back(k);
                continue;
            }
            k->subheap.push_back(rad[x]);
            rad[x]=k;
        }
        else
        if(C==2)
        {
            f>>x;
            g<<rad[x]->val<<'\n';
            heap_extract(x);
        }
        else
        {
            f>>x>>y;
            if(rad[y]==0)
                continue;
            if(rad[x]==0)
            {
                rad[x]=rad[y];
                continue;
            }
            heap_merge(rad[x],rad[y]);
        }
    }
    return 0;
}