// 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;
        }

  //      outputFile<<"merge intre "<<root->value<<" si "<<heap2.root->value<<'\n';

        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;
        }

/*
        outputFile<<"dupa merge: "<<root->value<<" cu urmatorul: "<<root->child->value;
        if(root->child->sibling != NULL) {outputFile<<" si urmatorul2: "<<root->child->sibling->value<<' ';

        if(root->child->sibling->sibling != NULL) outputFile<<" si urmatorul3: "<<root->child->sibling->sibling->value<<' ';
        }
        outputFile<<'\n';
        */
    }

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

   //     outputFile<<"incepe insert in heap "<<x<<" la "<<val<<'\n';

        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() {

    //    outputFile<<"twopass merge la "<<x<<" \n";

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

       //     outputFile<<" la "<<x<<" iese aici ----\n";
            
            return;
        }

        if (root->child->sibling == NULL) {
            root = root->child;                                     // Daca exista un singur subheap, devine noul heap principal
            
        //    outputFile<<" la "<<x<<" iese aici 0000\n";

            return;
        }

        vector<PairingHeap> pairs;
        int nrPairs = 0;

        Node* current = this->root->child;
        Node* currentSibling = this->root->child->sibling;
        Node* nextSibling = currentSibling->sibling;        // Variabila necesara pentru a nu pierde legatura catre urmatorul frate, daca exista
       
        do {                                                        // Acesta este primul pass, care cupleaza subheapurile cate doua (ultimul poate ramane necuplat)
          //  outputFile<<"primul e "<<current->value<<" al doilea e "<<currentSibling->value<<'\n';
         //   if(root->child->sibling->sibling != NULL) outputFile<<" urmatoru e: "<< this->root->child->sibling->sibling->value<<'\n';
             
            
            pairs.push_back(PairingHeap());                         

            PairingHeap siblingHeap = PairingHeap();

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

           // outputFile<<"primul e "<<pairs[nrPairs].root->value<<" al doilea e "<<siblingHeap.root->value<<'\n';
            
            pairs[nrPairs].mergeWith(siblingHeap);
            
            
           // outputFile<<"si dupa mergewith primul are max: "<<pairs[nrPairs].root->value<<'\n';

            if (nextSibling == NULL) {
                
            //    outputFile<<" la "<<x<<" iese aici 1111\n";
                
                ++nrPairs;
                break;
            }
            
            current = nextSibling;
            
            if (current->sibling == NULL) {
                ++nrPairs;

                
              //  outputFile<<" la "<<x<<" iese aici 2222\n";

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

            currentSibling = current->sibling;
            nextSibling = currentSibling->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 
        
     //   outputFile<<"root initial la "<<x<<':'<<'\n'<<this->root->value <<'\n';
    //    outputFile<<"nr pairs: "<<nrPairs<<'\n';
        for (int i = nrPairs - 2; i >= 0; --i) {
         //   outputFile<<"pair "<<pairs[i].getMax()<<'\n';
            this->mergeWith(pairs[i]);
            //outputFile<<"dupa merge root: "<<this->root->value<<'\n';
        }
        

    }

    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();
           // outputFile<<'\n';
        }

        if (tipOperatie == 1) {
            inputFile >> x >> y;
            listaHeapuri[x].insert(y);
            //outputFile<<"intra "<<y<<" in "<<x<<'\n';
        }

        if (tipOperatie == 3) {
            inputFile >> x >> y;
            
            //outputFile<<x<<" are max "<<listaHeapuri[x].getMax()<<' '<<y<<" are max "<<listaHeapuri[y].getMax()<<'\n';

            listaHeapuri[x].mergeWith(listaHeapuri[y]);

            listaHeapuri[y].root = NULL;

            //outputFile<<"dupa merge "<<x<< " are max "<<listaHeapuri[x].getMax()<<'\n';
        }
    }


    return 0;
}