#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 777777777ll
#define nmax 300001
using namespace std;
typedef long long ll;
//ifstream in("ghicit.in");
//ofstream out("cuba.out");
FILE *fin=fopen("mergeheap.in","r");
FILE *fout=fopen("mergeheap.out","w");
struct h{int v;h *d,*f;}e[nmax];
int n,q,i,j,k,l,x,y,c;h*m[101],*o[nmax];
inline h*r(h*a,h*b)
{
    if(a==0)return b;
    if(b==0)return a;
    if(a->v>b->v)
        {b->d=a->f,a->f=b;return a;}
        else{a->d=b->f,b->f=a;return b;}
}
int main()
{
fscanf(fin,"%d%d",&n,&q);
while(q--)
{
    fscanf(fin,"%d %d",&c,&x);
    if(c==3)
    {
        fscanf(fin,"%d",&y);
        m[x]=r(m[x],m[y]);
        m[y]=0;
    }
    else if(c==1)
    {
        fscanf(fin,"%d",&(e[++l].v));
        m[x]=r(m[x],&e[l]);
    }
    else{
        fprintf(fout,"%d\n",m[x]->v);
        if(m[x]->f)
        {
            j=0,o[0]=m[x]->f;
            while(o[j]->d)o[j+1]=o[j]->d,j++;
            for(i=0;i<j;i+=2)o[i]=r(o[i],o[i+1]);
            if(i!=j)i-=2;//j=3==>2,j=4=>4
            //printf("%dI\n",i);
            while(i>0)o[i-2]=r(o[i-2],o[i]),i-=2;
            o[0]->d=0,m[x]=o[0];
        }
        else m[x]=0;
    }
}
}