// Aceasta este o implementare a unui Pairing Heap(max-heap), realizata pentru Tema 3(structura complexa) din cadrul laboratorului de Structuri de Date
// De catre Podaru Eduard-Cristian, grupa 131

#include<iostream>
#include<fstream>
#include<vector>

using namespace std;


ifstream inputFile("mergeheap.in");
ofstream outputFile("mergeheap.out");

int n, q;           // Semnificatia din enuntul de pe infoarena

int tipOperatie;
int x, y;           // Variabile auxiliare pentru citire


class Node {
public:
    int value;
    Node* child;
    Node* sibling;

    Node() {
        child = NULL;
        sibling = NULL;
        value = 0;
    }

    Node(int valoare) {
        value = valoare;
        child = NULL;
        sibling = NULL;
    }

    Node(int valoare, Node* copil, Node* frate) {
        value = valoare;
        child = copil;
        sibling = frate;
    }
};

class PairingHeap {

public:
    Node* root;

    PairingHeap() {
        root = NULL;
    }

    PairingHeap(int x) {                                        // Constructor folositor pentru a face merge-uri cu un singur element
        Node* n = new Node(x);
        root = n;
    }

    bool empty() {
        return root == NULL;
    }

    void mergeWith(PairingHeap& heap2) {                         // Metoda folosita pentru merging, poate fi practic folosita si pentru insert-uri,
                                                                // deoarece putem merge-ui cu un heap cu un singur element
        if (heap2.empty()) {
            return;
        }

        if (this->empty()) {

            root = heap2.root;
            return;
        }

        if (this->root->value >= heap2.root->value) {
            heap2.root->sibling = this->root->child;            // Adaugam heap2 la lista de subheapuri 
            this->root->child = heap2.root;
            heap2.root = NULL;                                  // "Stergem" heap2, deoarece acum e legat de obiectul curent
        }
        else {
            this->root->sibling = heap2.root->child;            // Intai adaugam la heap2 obiectul curent in lista de subheapuri ale lui heap2
            heap2.root->child = this->root;
            this->root = heap2.root;                            // Preluam root-ul de la heap2, apoi il putem "sterge", deoarece s-a mutat in obiectul curent
            heap2.root = NULL;
        }


    }

    void insert(int x) {
        PairingHeap heap2 = PairingHeap(x);

        this->mergeWith(heap2);
    }

    int getMax() {
        return root->value;
    }

    void heapify(vector<int> listaElemente) {              // Metoda care primeste o lista de elemente si formeaza in obiectul curent un pairing heap care le contine

        int lungime = listaElemente.size();

        if (lungime) {                                      // Daca nu e gol
            Node* n = new Node(listaElemente[0]);
            this->root = n;

            for (int i = 1; i < lungime; ++i) {
                this->insert(listaElemente[i]);
            }
        }
    }

    void twoPassMerge() {
        if (root->child == NULL) {                                   // Daca exista un singur nod(radacina), heapul ramane gol
            root = NULL;
            return;
        }

        if (root->child->sibling == NULL) {
            root = root->child;                                     // Daca exista un singur subheap, devine noul heap principal
            return;
        }

        vector<PairingHeap> pairs;
        int nrPairs = 0;

        Node* current = this->root->child;
        Node* currentSibling = this->root->child->sibling;

        do {                                                        // Acesta este primul pass, care cupleaza subheapurile cate doua (ultimul poate ramane necuplat)
            pairs.push_back(PairingHeap());                         

            PairingHeap siblingHeap = PairingHeap();

            pairs[nrPairs].root = current;
           // pairs[nrPairs].root->sibling = NULL;

            siblingHeap.root = currentSibling;
            //siblingHeap.root->sibling = NULL;

            pairs[nrPairs].mergeWith(siblingHeap);

            if (currentSibling->sibling == NULL) {
                ++nrPairs;
                break;
            }
            
            current = currentSibling->sibling;
            
            if (current->sibling == NULL) {
                ++nrPairs;

                pairs.push_back(PairingHeap());
                pairs[nrPairs].root = current;
                
                ++nrPairs;
                break;
            }

            currentSibling = current->sibling;

            ++nrPairs;
        } while (current != NULL);

        this->root = pairs[nrPairs - 1].root;                         // La al doilea pass luam de la dreapta la stanga perechile si le tot merge-uim succesiv
                                                                    // Luand mereu rezultatul ultimului merge si urmatorul pair din stanga 
        for (int i = nrPairs - 2; i >= 0; --i) {
            this->mergeWith(pairs[i]);
        }

    }

    void deleteMax() {                                              // Pentru a sterge maximul, folosim un two-pass merge/two-pass pairing
        if (!this->empty()) {
            this->twoPassMerge();
        }
    }


};

vector<PairingHeap> listaHeapuri;

int main() {

    inputFile >> n >> q;

    for (int i = 0; i <= n; ++i) {
        listaHeapuri.push_back(PairingHeap());
    }

    for (int i = 0; i < q; ++i) {

        inputFile >> tipOperatie;

        if (tipOperatie == 2) {
            inputFile >> x;
            outputFile << listaHeapuri[x].getMax()<<'\n';
            listaHeapuri[x].deleteMax();
        }

        if (tipOperatie == 1) {
            inputFile >> x >> y;
            listaHeapuri[x].insert(y);
        }

        if (tipOperatie == 3) {
            inputFile >> x >> y;
            listaHeapuri[x].mergeWith(listaHeapuri[y]);
        }
    }


    return 0;
}