#include <iostream>
#include <fstream>

using namespace std;

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

struct Nod{
    int valoare;
    Nod *fiuStanga;
    Nod *frate;
};

struct PairHeap{
    Nod *rad;
};

bool isEmpty(PairHeap heap){
    return heap.rad == NULL;
}

int getMax(PairHeap heap){
    return heap.rad->valoare;
}

void Merge(PairHeap heap1, PairHeap heap2){
                    //vom face in heapul 1 reuniunea dintre heapul 1 si heapul 2, iar heapul 2 va iesi gol
            //daca heapul 1 este gol, doar mutam heapul 2 in heapul 1
    if(heap1.rad == NULL){
        heap1.rad = heap2.rad;
        heap2.rad = NULL;
        return;
    }
            //daca heapul 2 este gol, rezultatul este deja in heapul 1
    if(heap2.rad == NULL){
        return;
    }
            //cum rezultatul reuniunii va fi in heap1, trebuie sa aducem in radacina maximul dintre radacinile celor 2 heapuri
    if(heap1.rad->valoare < heap2.rad->valoare){
        swap(heap1.rad, heap2.rad);
    }
            //infratim radacina heapului 2 cu fiii heapului 1, aducand astfel heapul 2 la un loc cu heapul 1 in timp ce pastram proprietatea de max heap
    heap2.rad->frate = heap1.rad->fiuStanga;
    heap1.rad->fiuStanga = heap2.rad;
            //golim heapul 2
    heap2.rad = NULL;
}

void insertHeap(PairHeap heap, int val){
            //creem un nou heap care are doar radacina (nodul cu valoarea trebuie inserata in heapul nostru)
    PairHeap heapNou;
    Nod *newNode;
    newNode->valoare = val;
    newNode->fiuStanga = NULL;
    newNode->frate = NULL;
    heapNou.rad=newNode;
            //facem reuniunea dintre heapul nou, format doar din nodul cu valoarea  de inserat, si heapul nostru
    Merge(heap, heapNou);
}

void buildHeapify(PairHeap heap, int n, int valori[]){
            //luam fiecare valoare si ii inseram nodul corespunzator in heap
    for(int i=0; i<n; i++){
        insertHeap(heap, valori[i]);
    }
}

PairHeap extrageMax(PairHeap heap){
    if(heap.rad->fiuStanga == NULL || heap.rad->fiuStanga->frate == NULL){
        heap.rad = heap.rad->fiuStanga;
        return heap;
    }
    PairHeap heap1, heap2, newHeap;
    heap1.rad = heap.rad->fiuStanga;
    heap2.rad = heap.rad->fiuStanga->frate;
    newHeap.rad = heap.rad->fiuStanga->frate->frate;

    Merge(heap1,heap2);
    newHeap = extrageMax(newHeap);
    Merge(heap1, heap);
    return heap1;
}

/*
void extrageMinim(PairHeap heap){
                //daca heapul este gol, nu avem ce extrage
    if(heap.rad == NULL){
        return;
    }
                //daca heapul are doar radacina sau radacina are un singur nod, trebuie doar sa stergem radacina
    if(heap.rad->fiuStanga == NULL || heap.rad->fiuStanga->frate == NULL){
        heap.rad = heap.rad->fiuStanga;
        return;
    }
    PairHeap heap1, heap2;
    Nod *a;
    a = heap.rad->fiuStanga;
    heap1.rad = heap.rad->fiuStanga;
    while(a != NULL){
        heap2.rad = a->frate;
        heap1 = Merge(heap1, heap2);
        a = a->frate;
    }
    heap.rad = heap.rad->fiuStanga;
}
*/

PairHeap v[10000];

int main()
{
    int n,q,cnt,cnt1,cnt2,x;
    int operatie;
    f>>n>>q;
    for(int i=0; i<q; i++){
        f>>operatie;
        if(operatie == 1){
            f>>cnt>>x;
            insertHeap(v[cnt],x);
        }
        if(operatie == 2){
            f>>cnt;
            g<<getMax(v[cnt]);
            extrageMax(v[cnt]);
        }
        if(operatie == 3){
            f>>cnt1>>cnt2;
            Merge(v[cnt1],v[cnt2]);
            v[cnt2].rad = NULL;
        }
    }
    return 0;
}