#include <bits/stdc++.h>

using namespace std;

ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");

struct nod {
    int valoare;
    int nivel;
    nod *parinte = nullptr;
    nod *fiu = nullptr;
    nod *stanga = nullptr;
    nod *dreapta = nullptr;
};

struct fibonacci {
    nod *maxi = nullptr;
    int nrHeapuri = 0;
};

nod *insert(nod *maxi, int &nr, int valoare) {
    nod *nodNou = new nod;
    nodNou->valoare = valoare;
    nodNou->nivel = 0;
    nodNou->stanga = nodNou;
    nodNou->dreapta = nodNou;
    if (maxi != nullptr) {
        (maxi->stanga)->dreapta = nodNou;
        nodNou->dreapta = maxi;
        nodNou->stanga = maxi->stanga;
        maxi->stanga = nodNou;
        if (nodNou->valoare > maxi->valoare)
            maxi = nodNou;
    } else {
        maxi = nodNou;
    }
    nr += 1;
    return maxi;
}

void conexiune(fibonacci *heap, nod *nod1, nod *nod2) {
    nod1->dreapta->stanga = nod1->stanga;
    nod1->stanga->dreapta = nod1->dreapta;

    if (nod2->dreapta == nod2)
        heap->maxi = nod2;

    nod1->stanga = nod1;
    nod1->dreapta = nod1;
    nod1->parinte = nod2;

    if (nod2->fiu == nullptr) {
        nod2->fiu = nod1;
    }
    nod1->dreapta = nod2->fiu;
    nod1->stanga = nod2->fiu->stanga;
    nod2->fiu->stanga->dreapta = nod1;
    nod2->fiu->stanga = nod1;
    if ((nod1->valoare) > (nod2->fiu->valoare))
        nod2->fiu = nod1;

    nod2->nivel += 1;
}

void actualizare(fibonacci *heap) {
    int nivele, index, nivel;
    nivele = int((log(heap->nrHeapuri)) / (log(2)));
    nod *noduri[nivele], *nod1, *nod2;
    for (index = 0; index <= nivele; index++) {
        noduri[index] = nullptr;
    }
    nod1 = heap->maxi;
    do {
        nivel = nod1->nivel;
        while (noduri[nivel] != nullptr) {
            nod2 = noduri[nivel];
            if (nod1->valoare > nod2->valoare) {
                swap(nod1, nod2);
            }
            if (nod2 == heap->maxi)
                heap->maxi = nod1;
            conexiune(heap, nod2, nod1);
            if (nod2->dreapta == nod1)
                heap->maxi = nod1;
            noduri[nivel] = nullptr;
            nivel++;
        }
        noduri[nivel] = nod1;
        nod1 = nod1->dreapta;
    } while (nod1 != heap->maxi);

    heap->maxi = nullptr;
    for (index = 0; index < nivele; index++) {
        if (noduri[index] != nullptr) {
            noduri[index]->stanga = noduri[index];
            noduri[index]->dreapta = noduri[index];
            if (heap->maxi == nullptr) {
                heap->maxi = noduri[index];
            } else {
                heap->maxi->stanga->dreapta = noduri[index];
                noduri[index]->dreapta = heap->maxi;
                noduri[index]->stanga = heap->maxi->stanga;
                heap->maxi->stanga = noduri[index];
                if (noduri[index]->valoare > heap->maxi->valoare) {
                    heap->maxi = noduri[index];
                }
            }
            if (heap->maxi == nullptr) {
                heap->maxi = noduri[index];
            } else if (noduri[index]->valoare > heap->maxi->valoare) {
                heap->maxi = noduri[index];
            }
        }
    }
}

nod *maxim(fibonacci *heap) {
    if (!heap->maxi) {
        nod *maxx = heap->maxi;
        nod *copie = maxx;
        nod *maxFiu = nullptr;
        if (maxx->fiu != NULL) {
            maxFiu = maxx->fiu;
            do {
                copie = maxFiu->dreapta;
                (heap->maxi->stanga)->dreapta = maxFiu;
                maxFiu->dreapta = heap->maxi;
                maxFiu->stanga = heap->maxi->stanga;
                heap->maxi->stanga = maxFiu;
                if (maxFiu->valoare > heap->maxi->valoare)
                    heap->maxi = maxFiu;
                maxFiu->parinte = nullptr;
                maxFiu = copie;
            } while (copie != maxx->fiu);
        }

        (maxx->stanga)->dreapta = maxx->dreapta;
        (maxx->dreapta)->stanga = maxx->stanga;
        heap->maxi = maxx->dreapta;

        if (maxx == maxx->dreapta && maxx->fiu == nullptr)
            heap->maxi = nullptr;
        else {
            heap->maxi = maxx->dreapta;
            actualizare(heap);
        }
        heap->nrHeapuri = heap->nrHeapuri - 1;
        return maxx;
    }
    return heap->maxi;
}

fibonacci *reuniune(fibonacci *heap1, fibonacci *heap2) {
    fibonacci *heap;
    heap->nrHeapuri = 0;
    heap->maxi = heap1->maxi;

    nod *maxx1, *maxx2;
    maxx1 = heap1->maxi->dreapta;
    maxx2 = heap2->maxi->stanga;

    heap->maxi->dreapta->stanga = heap2->maxi->stanga;
    heap->maxi->dreapta = heap2->maxi;
    heap2->maxi->stanga = heap->maxi;
    maxx2->dreapta = maxx1;

    if ((heap1->maxi == nullptr) || (heap2->maxi != nullptr && heap2->maxi->valoare < heap1->maxi->valoare)) {
        heap->maxi = heap2->maxi;
    }
    heap->nrHeapuri = heap1->nrHeapuri + heap2->nrHeapuri;
    return heap;
}

int main() {
    int index, nrMultimi, nrOperatii, operatie, multime1, multime2, valoare;
    fin >> nrMultimi >> nrOperatii;
    vector<fibonacci> fiboHeap(nrMultimi + 1);
    for (index = 0; index < nrOperatii; index += 1) {
        fin >> operatie;
        switch (operatie) {
            case 1:
                fin >> multime1 >> valoare;
                fiboHeap[multime1].maxi = insert(fiboHeap[multime1].maxi, fiboHeap[multime1].nrHeapuri, valoare);
                break;
            case 2:
                fin >> multime1;
                fout << maxim(&fiboHeap[multime1])->valoare << "\n";
                break;
            case 3:
                fin >> multime1 >> multime2;
                fiboHeap[multime1] = *reuniune(&fiboHeap[multime1], &fiboHeap[multime2]);
                break;

        }
    }
    return 0;
}