#include <iostream>
#include <fstream>
using namespace std;
ifstream f("mergeheap.in");
ofstream g("mergeheap.out");


struct nod
{
    int val;
    nod *copil, *frate;
    nod(int x)
    {   val=x;
        copil=NULL;
        frate=NULL;
    }
};

struct Pairing_Heap
{
    nod *rad;
    Pairing_Heap()
    {
        rad=NULL;
    }
    Pairing_Heap(nod *ob)
    {
        rad=ob;
    }
    Pairing_Heap(int v1)
    {
        rad= new nod(v1);
    }
    nod *merge_heap(nod *heap1, nod *heap2)
    {   if(heap1==NULL)
        {
            heap1=heap2;
            return heap1;
        }
        if(heap2==NULL)
        {
            return heap1;
        }
        if(heap1->val<heap2->val)
        {   nod *aux=heap1;
            heap1=heap2;
            heap2=aux;
        }
        heap2->frate=heap1->copil;
        heap1->copil=heap2;
        return heap1;
    }
    void merge_heap(Pairing_Heap ob)
    {
        if(rad==NULL)
        {
            rad=ob.rad;
            return;
        }
        if(ob.rad==NULL)
        {
            return;
        }
        if(rad->val<ob.rad->val)
        {   nod *aux=rad;
            rad=ob.rad;
            ob.rad=aux;
        }
        ob.rad->frate=rad->copil;
        rad->copil=ob.rad;
        ob.rad=NULL;
    }
    nod *two_pass_merge(nod *ob)
    {   if(ob==NULL || ob->frate==NULL)
            return ob;
        nod *heap1,*heap2,*urmat;
        heap1=ob;
        heap2=ob->frate;
        urmat=ob->frate->frate;
        heap1->frate=heap2->frate=NULL;
        return merge_heap(merge_heap(heap1,heap2),two_pass_merge(urmat));
    }
    void add(int v1)
    {
        merge_heap(Pairing_Heap(v1));
    }
    int pop()
    {   int amogus=rad->val;
        nod *aux=rad;
        rad=two_pass_merge(rad->copil);
        delete aux;
        return amogus;
    }
    void unire(Pairing_Heap &ob)
    {   merge_heap(ob);
        ob.rad=NULL;
    }
};
Pairing_Heap v[1000];
int n,q,op,x,p1,p2;
int main()
{   f>>n>>q;
    for(int i=1;i<=q;i++)
    {   f>>op;
        if(op==1)
        {   f>>p1>>x;
            v[p1].add(x);
        }
        if(op==2)
        {   f>>p1;
            g<<v[p1].pop()<<'\n';
        }
        if(op==3)
        {   f>>p1>>p2;
            v[p1].unire(v[p2]);
        }
    }
    f.close();
    g.close();
    return 0;
}