#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_extract(int x)
{
    if(rad[x]->subheap.size()==0)
    {
        rad[x]=0;
        return;
    }
    heap *k=new heap;
    heap *v=new heap;
    k=rad[x]->subheap[0];
    int n=rad[x]->subheap.size();
    for(int i=1;i<n;i++)
    {
        v=rad[x]->subheap[i];
        if(v->val>k->val)
            swap(k,v);
        k->subheap.push_back(v);
    }
    rad[x]=k;
}
void heap_merge(int x,int y)
{
    if(rad[y]==0)
        return;
    if(rad[x]==0)
        {
            rad[x]=rad[y];
            return;
        }
    if(rad[x]->val<rad[y]->val)
        swap(rad[x],rad[y]);
    rad[x]->subheap.push_back(rad[y]);
    rad[y]=0;
    return;
}
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;
            heap_insert(x,k);
        }
        else
        if(C==2)
        {
            f>>x;
            g<<rad[x]->val<<'\n';
            heap_extract(x);
        }
        else
        {
            f>>x>>y;
            heap_merge(x,y);
        }
    }
    return 0;
}