//# OBS: Resursa care m-a ajutat destul de mult sa inteleg acest tip de heap
//# prin conexiune cu linked lists si binary heaps este:
//# http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm  (cartea Cormen)
//
//# Heap-urile de tip Fibonacci au noduri radacina (in cadrul unei liste dublu inlantuite circulare de noduri)
//# care insa nu sunt neaparat ordonate
//
//# --> fiecare nod contine un pointer catre parintele sau si un alt pointer catre unul dintre copiii sai
//# ---> copiii fac parte dintr-o lista dublu inlantuita circulara (aka "kids list")
//#  in acest mod, ficare copil are pointer catre fratii sai de stanga si dreapta
//#  dc nu ar avea frati si ar fi singur la parinti atunci pointer-ul de stanga si de dreapta ar coincide cu copilul respectiv
//
//#  nodurile radacina sunt lincuite prin intermediul listei dublu inlantuite circulare cu ajutorul pointer-ilor de dreapta si de stanga
//
//#  De ce lista dublu inlantuita circular? ... fiindca scoaterea sau inserarea de elem este in O(1)
//#  si daca vreau sa lipesc doua astefel de liste o pot face in O(1)
//import math;
//
//
//# in esenta un Fib heap ca si constuctie e ca o serie de heap-uri
//#  avand radacinile pe fiecare nivel intr-un double linked list circular
//

// OBS: am implementat initial in Python,
// nu am inteles ca trebuie implementat direct pe probl de info arena
// cumva am incercat sa adaptez in timp scurt


#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <fstream>
using namespace std;

ifstream finput("mergeheap.in");
ofstream foutput("mergeheap.out");


struct Fib_Heap_Node
{
        int key; // adica valoarea asociata nodului
        Fib_Heap_Node* left;
        Fib_Heap_Node* right;

        Fib_Heap_Node* parent;
        Fib_Heap_Node* child;

        int degree;
//        vreau sa marchez nodul care e un loser
        bool mark;
       // int id; // vizualizez in esenta un graf si am un id pe vertex
    };


    class Fib_Heap {
    public:
        Fib_Heap_Node* min_Node;
        int num_Nodes;

        Fib_Heap(){
        // am constructorul de initializare, cu pointer-ul pt nodul minim
        // pe care il initializez la null prin null pointer
            min_Node = nullptr;
            num_Nodes = 0;
        }

        ~Fib_Heap() {
            _clear(min_Node);
        }

//        inserez un nod cu val de new_key
        Fib_Heap_Node* insert(int new_key);
        void merge_heaps(Fib_Heap& another_H);
        Fib_Heap_Node* merge_nodes(Fib_Heap_Node* a, Fib_Heap_Node* b);

        void _insert_node(Fib_Heap_Node *newNode);
        Fib_Heap_Node *_merge(Fib_Heap_Node *a, Fib_Heap_Node *b);


        Fib_Heap_Node* _create_node(int newKey);

        int remove_min();
        void add_child(Fib_Heap_Node* parent, Fib_Heap_Node* child);

        // Adica reconstructie de heap odata cu scoatere de nod
        void cascading_cut(Fib_Heap_Node* x);
        Fib_Heap_Node* remove_min(Fib_Heap_Node* x);

        void _clear(Fib_Heap_Node* x);


    };


Fib_Heap_Node* Fib_Heap::insert(int newKey)
{
    Fib_Heap_Node* newNode = _create_node(newKey);
    _insert_node(newNode);
    return newNode;
}

Fib_Heap_Node* Fib_Heap::_create_node(int newKey)
{
    Fib_Heap_Node* newNode = new Fib_Heap_Node;
    newNode->key = newKey;
    newNode->left = newNode;
    newNode->right = newNode;
    newNode->parent = nullptr;
    newNode->child = nullptr;
    newNode->degree = 0;
    newNode->mark = false;
    return newNode;
}

// aka Cormen, inserarea implica un merge de root nodes si repozitionare pe minim de heap
void Fib_Heap::_insert_node(Fib_Heap_Node* newNode) {
    min_Node = _merge(min_Node, newNode);
    num_Nodes++;
}

void Fib_Heap::merge_heaps(Fib_Heap &another_H){
    min_Node = merge_nodes(min_Node, another_H.min_Node);
//    num_Nodes += another_H.num_Nodes;
    another_H.min_Node = nullptr;
//    another_H.num_Nodes = 0;
}

Fib_Heap_Node* Fib_Heap::merge_nodes(Fib_Heap_Node* a, Fib_Heap_Node* b)
{
    if(a == NULL)
        return b;
    if(b == NULL)
        return a;
    if(a->key > b->key)
    {
        Fib_Heap_Node* temp = a;
        a = b;
        b = temp;
    }
    Fib_Heap_Node* a_right = a->right;
    Fib_Heap_Node* b_left = b->left;
    a->right = b;
    b->left = a;
    a_right->left = b_left;
    b_left->right = a_right;
    return a;
}


Fib_Heap_Node* Fib_Heap::_merge(Fib_Heap_Node* a, Fib_Heap_Node* b)
{
    if(a == nullptr)
        return b;
    if(b == nullptr)
        return a;
    if( a->key > b->key ) // swap node
    {
        Fib_Heap_Node* temp = a;
        a = b;
        b = temp;
    }
    Fib_Heap_Node* aRight = a->right;
    Fib_Heap_Node* bLeft = b->left;
    a->right = b;
    b->left = a;
    aRight->left = bLeft;
    bLeft->right = aRight;
    return a;
}

int Fib_Heap::remove_min()
{
    Fib_Heap_Node* old = min_Node;
    min_Node = remove_min(min_Node);
    int ret = old->key;
    delete old;
    return ret;
}


void Fib_Heap::add_child(Fib_Heap_Node* parent, Fib_Heap_Node* child)
{
    child->left = child->right = child;
    child->parent = parent;
    parent->degree++;
    parent->child = merge_nodes(parent->child,child);
}


// mark este un flag cu privire la pierderea de copii anterior
// in acest mod va avea loc un sloce pe nodul respectiv... de unde si numele de cascading_cut

void Fib_Heap::cascading_cut(Fib_Heap_Node* x)
{
    if(x == NULL)
        return;
    Fib_Heap_Node* c = x;
    do
    {
        c->mark = false;
        c->parent = NULL;
        c = c->right;
    }
    while(c != x);
}


Fib_Heap_Node* Fib_Heap::remove_min(Fib_Heap_Node* x)
{
    cascading_cut(x->child);
    if(x->right == x)
    {
        x = x->child;
    }
    else
    {
        x->right->left = x->left;
        x->left->right = x->right;
        x = merge_nodes(x->right,x->child);
    }
    if(x == NULL)
        return x;
    Fib_Heap_Node* Temp[64] = {NULL};
    while(true)
    {
        if(Temp[x->degree] != NULL)
        {
            Fib_Heap_Node* t = Temp[x->degree];
            if(t == x)
                break;
            Temp[x->degree] = NULL;
            if(x->key < t->key)
            {
                t->left->right = t->right;
                t->right->left = t->left;
                add_child(x,t);
            }
            else
            {
                t->left->right = t->right;
                t->right->left = t->left;
                if(x->right == x)
                {
                    t->right = t->left = t;
                    add_child(t,x);
                    x = t;
                }
                else
                {
                    x->left->right = t;
                    x->right->left = t;
                    t->right = x->right;
                    t->left = x->left;
                    add_child(t,x);
                    x = t;
                }
            }
            continue;
        }
        else
        {
            Temp[x->degree] = x;
        }
        x = x->right;
    }
    Fib_Heap_Node* Min = x;
    Fib_Heap_Node* temp = x;
    do
    {
        if(x->key < Min->key)
            Min = x;
        x = x->right;
    }
    while(x != temp);
    return Min;
}


void Fib_Heap::_clear(Fib_Heap_Node* x)
{
    if ( x != nullptr )
    {
        Fib_Heap_Node* t1 = x;
        do{
            Fib_Heap_Node* t2 = t1;
            t1 = t1->right;
            _clear(t2->child);
            delete t2;
        } while(t1 != x);
    }
}

int main() {
    int nrHeaps, nrop;
    finput >> nrHeaps >> nrop;
    Fib_Heap vec_heaps[nrHeaps + 1];
    for (int i = 0; i < nrop; i++) {
        int tip, x, a, b;
        finput >> tip;

        if (tip == 1) {
            finput >> a >> b;
//  gandesc in termeni de max heap
            vec_heaps[a].insert(-b);
        } else if (tip == 2) {
            finput >> x;
            foutput << -vec_heaps[x].min_Node->key << '\n';
            vec_heaps[x].remove_min();
        } else if (tip == 3) {
            finput >> a >> b;
            vec_heaps[a].merge_heaps(vec_heaps[b]);
        }
    }
    return 0;
}



//Fib_Heap_Node *Fib_Heap::merge_nodes(Fib_Heap_Node *a, Fib_Heap_Node *b) {
//    return nullptr;
//}