#include <bits/stdc++.h>

using namespace std;

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

class Nod {
public:
    Nod(int);

    friend class Fibonacci;

private:
    int valoare;
    int nivel;
    vector<Nod *> fiu;
    Nod *parinte;
    Nod *stanga;
    Nod *dreapta;
};

Nod::Nod(int valoare) {
    this->valoare = valoare;
    this->nivel = 0;
    this->parinte = nullptr;
    this->stanga = nullptr;
    this->dreapta = nullptr;
}

class Fibonacci {
public:
    Fibonacci();

    void inserare(int);

    void inserare(Nod *);

    void reuniune(Fibonacci &);

    int maxim();

    void stergere();

private:
    Nod *max;

    int nrHeapuri;
};

Fibonacci::Fibonacci() {
    max = nullptr;
    nrHeapuri - 0;
}


void Fibonacci::inserare(int valoare) {
    if (!max) {
        max = new Nod(valoare);
        max->stanga = max;
        max->dreapta = max;
    } else {
        Nod *maxx = max->dreapta;
        Nod *nodNou = new Nod(valoare);
        max->dreapta = nodNou;
        maxx->stanga = nodNou;
        nodNou->stanga = max;
        nodNou->dreapta = maxx;
        if (nodNou->valoare > max->valoare)
            max = nodNou;
    }
    nrHeapuri += 1;

}

void Fibonacci::inserare(Nod *n) {
    if (!max) {
        max = n;
        max->stanga = n;
        max->dreapta = n;
    } else {
        Nod *maxx = max->dreapta;
        Nod *nodNou = n;
        max->dreapta = nodNou;
        maxx->stanga = nodNou;
        nodNou->stanga = max;
        nodNou->dreapta = maxx;
        if (nodNou->valoare > max->valoare)
            max = nodNou;
    }
    nrHeapuri += 1;
}

void Fibonacci::reuniune(Fibonacci &heap) {
    if (!heap.max)
        return;
    if (!max) {
        *this = heap;
        return;
    }
    nrHeapuri += heap.nrHeapuri;
    heap.nrHeapuri = 0;
    Nod *dr = max->dreapta;
    Nod *stFinal = heap.max->stanga;
    max->dreapta = heap.max;
    heap.max->stanga = max;
    dr->stanga = stFinal;
    stFinal->dreapta = dr;
    if (heap.max->valoare > this->max->valoare)
        this->max = heap.max;
    heap.max = nullptr;
}

int Fibonacci::maxim() {
    return max->valoare;
}

void Fibonacci::stergere() {
    if (!max)
        return;
    if (max->stanga == max && max->fiu.size() == 0) {
        delete max;
        max = nullptr;
        nrHeapuri = 0;
        return;
    }
    for (auto subHeap: max->fiu)
        this->inserare(subHeap);
    max->dreapta->stanga = max->stanga;
    max->stanga->dreapta = max->dreapta;
    Nod *copie = max;
    max = max->dreapta;
    delete copie;
    nrHeapuri -= 1;
    vector<Nod *> ordine(log2(nrHeapuri) + 1, nullptr);
    ordine[max->nivel] = max;
    Nod *index = max->dreapta;
    Nod *final = max;
    while (index != final) {
        Nod *heapNou = index;
        while (ordine[heapNou->nivel] != nullptr) {
            Nod *radacina = ordine[heapNou->nivel];
            if (heapNou->valoare >= radacina->valoare) {
                heapNou->fiu.push_back(radacina);
                radacina->parinte = heapNou;
                ordine[heapNou->nivel] = nullptr;
                heapNou->nivel += 1;
            } else {
                radacina->fiu.push_back(heapNou);
                heapNou->parinte = radacina;
                ordine[heapNou->nivel] = nullptr;
                radacina->nivel += 1;
                heapNou = radacina;
            }
        }
        ordine[heapNou->nivel] = heapNou;
        index = index->dreapta;
    }
    max = nullptr;
    for (auto elem: ordine)
        if (elem) {
            this->inserare(elem);
            if (elem->valoare > max->valoare)
                max = elem;
        }
}

int main() {
    int operatie, nrHeapuri, nrOperatii, index;
    fin >> nrHeapuri >> nrOperatii;
    int multime1, multime2;
    vector<Fibonacci> heapuri(nrHeapuri + 1);
    for (index = 0; index < nrOperatii; index++) {
        fin >> operatie;
        if (operatie == 1) {
            fin >> multime1 >> multime2;
            heapuri[multime1].inserare(multime2);
        } else if (operatie == 2) {
            fin >> multime1;
            fout << heapuri[multime1].maxim() << "\n";
            heapuri[multime1].stergere();
        } else if (operatie == 3) {
            fin >> multime1 >> multime2;
            heapuri[multime1].reuniune(heapuri[multime2]);
        }
    }
    return 0;
}