#include<bits/stdc++.h>
using namespace std;

struct node{
    int root; //retine radacina
    int degree; //retine numarul copiilor
    node *parent; //pointer catre parinte
    node *child; //pointer catre left-child
    node *sibling; //pointer catre right-child
};

node* newNode(int key){
    //se aloca memorie pentru un nou nod
    node *aux = new node;
    aux->root = key;
    aux->degree = 0;
    aux->child = NULL;
    aux->parent = NULL;
    aux->sibling = NULL;
    return aux;
}

///------------------------------------------------------------------


node* mergeTrees(node *b_tree1, node *b_tree2){
    /// aici e merge operation intre arbori
    /// (ne va ajuta la adjust => dupa ce extragem/adaugam un elem, trb sa reconstruim heap-ul)

    //ma asigur ca tree1 are radacina mai mica
    if (b_tree1->root > b_tree2->root)
        swap(b_tree1, b_tree2);

    //punem tree-ul cu radacina mai mare (tree2)
    //ca fiu strang al celui cu radacina mica
    b_tree2->parent = b_tree1;
    b_tree2->sibling = b_tree1->child;
    b_tree1->child = b_tree2;
    b_tree1->degree++;

    return b_tree1;
}


///------------------------------------------------------------------------


list<node*> unionHeaps(list<node*> Heap1, list<node*> Heap2){

    list<node*> newHeap; //newHeap retine heap-ul binomial obtinut din combinarea celor doua

    list<node*>::iterator h1_begin = Heap1.begin();
    list<node*>::iterator h2_begin = Heap2.begin();

    while (h1_begin != Heap1.end() && h2_begin != Heap2.end()){

        // daca gradul lui heap1 <= gradul lui heap2, hewHeap retine primul elem (arbore) din heap1
        if((*h1_begin)->degree <= (*h2_begin)->degree){
            newHeap.push_back(*h1_begin);
            h1_begin++;
        }

            // altfel, hewHeap retine primul element (arbore) din heap2
        else
        {
            newHeap.push_back(*h2_begin);
            h2_begin++;
        }
    }

    //daca au ramas elemente in heap1, le punem in newHeap
    while (h1_begin != Heap1.end()){
        newHeap.push_back(*h1_begin);
        h1_begin++;
    }


    //daca au mai ramas elemenre in heap2, le punem in newHeap
    while (h2_begin != Heap2.end()){
        newHeap.push_back(*h2_begin);
        h2_begin++;
    }

    return newHeap;
}

///-----------------------------------------------------------------


list<node*> adjustHeap(list<node*> b_heap)
{
    /// functia adjust se asigura ca cele 2 conditii ale b_heap-ului binomial sunt respectate
    /// (nu exista 2 arbori binomiali cu acelasi grad si elem sunt ordonate cresc)

    if (b_heap.size() <= 1)
        return b_heap;

    list<node*> new_heap;
    list<node*>::iterator it1, it2, it3;

    //se porneste cu 3 iteratori
    it1 = b_heap.begin();
    it2 = b_heap.begin();
    it3 = b_heap.begin();

    //daca heap-ul are doar 2 elem retinem asta (it3 aj la final) altfel fiecare ia 3 poz consecutive
    if (b_heap.size() == 2){
        it2++;
        it3 = b_heap.end();
    }
    else
    {
        it2++;
        it3 = it2;
        it3++;
    }

    ///cat timp nu s-a ajuns a final cu prmil index

    while (it1 != b_heap.end()){
        // daca a ramas doar un element care trb procesat, it1 creste
        if (it2 == b_heap.end())
            it1++;

            // altfel, daca primul arebore are mai putini copii decat al doilea
            // operatia de merge a arborilor e imposibila, deci incrementam indecsii
        else if ((*it1)->degree < (*it2)->degree)
        {
            it1++;
            it2++;
            if(it3 != b_heap.end())
                it3++;
        }


            //daca cele 3 elem pointate de cei 3 indecsi sunt egale ca nr de copii din heap (sunt la fel)
            //incrementam indecsii
        else if (it3 != b_heap.end() && (*it1)->degree == (*it2)->degree && (*it1)->degree == (*it3)->degree)
        {
            it1++;
            it2++;
            it3++;
        }

            // Daca doar primii 2 arbori sunt 'la fel' (au acelasi nr de copii)
            //facem merge la cei 2 arbori
            //stergem al doilea arbore din heap
            //incrememtam it3 daca acesta n a aj la final
        else if ((*it1)->degree == (*it2)->degree)
        {
            *it1 = mergeTrees(*it1,*it2);
            it2 = b_heap.erase(it2);
            if(it3 != b_heap.end())
                it3++;
        }
    }

    return b_heap;
}


///------------------------------------------------------------


list<node*> insertATreeInHeap(list<node*> _heap, node *tree)
{
    ///se insereaza un arbore in heap-ul binomial (teoretic un element)

    list<node*> heap_aux;

    // inseram in heap-ul auxiliar arborele
    heap_aux.push_back(tree);

    //folosim operatia union pentru a insera arborele in heap.ul original
    heap_aux = unionHeaps(_heap, heap_aux);

    //folosim adjust pentru a aranja elementele in ordinea coresp.
    heap_aux = adjustHeap(heap_aux);

    return heap_aux;
}


///----------------------------------------------------


list<node*> removeMinFromTree(node *tree)
{
    ///functie  care ne va ajuta la operatia getMin
    //primeste ca parametru arborele cu radacina minima
    //sterge radacina din arbore si un heap format din elem arborelui

    list<node*> heap;
    node *child_ = tree->child;
    node *val;

    while (child_)
    {
        val = child_;
        child_ = child_->sibling;
        val->sibling = NULL;
        heap.push_front(val);
    }

    return heap;
}

///------------------------------------------------------------

list<node*> removeMaxFromTree(node *tree)
{
    ///functie  care ne va ajuta la operatia getMax
    //primeste ca parametru arborele cu val maxima
    //sterge val din arbore si returneaza un heap format din elem arborelui

    list<node*> heap;
    node *child_ = tree->child;
    node *val;

    while (child_)
    {
        val = child_;
        child_ = child_->sibling;
        val->sibling = NULL;
        heap.push_front(val);
    }

    return heap;
}

///------------------------------------------------------------

list<node*> insert(list<node*> _head, int key)
{
    node *temp = newNode(key);
    return insertATreeInHeap(_head,temp);
}


///----------------------------------------------------------------


node* getMin(list<node*> _heap)
{

    auto it = _heap.begin();
    node *min = *it;

    while (it != _heap.end())
    {
        if ((*it)->root < min->root)
            min = *it;
        it++;
    }

    cout << "\n elemenul minim e: " <<   min->root << endl;

    return min;
}


///--------------------------------------------------------


list<node*> extractMin(list<node*> _heap)
{
    list<node*> new_heap,tree_min;
    node *min;

    //min pointeaza la arborele cu cea mai mica radacina din heap
    min = getMin(_heap);
    auto it = _heap.begin();
    while (it != _heap.end()){
        if (*it != min){
            new_heap.push_back(*it);
        }
        it++;
    }

    tree_min = removeMinFromTree(min);
    new_heap = unionHeaps(new_heap, tree_min);
    new_heap = adjustHeap(new_heap);

    return new_heap;
}


///------------------------------------------------------------



void printTree(node *h){
    while (h){
        cout << h->root<< " ";
        printTree(h->child);
        h = h->sibling;
    }
}

///------------------------------------------------------------


void printHeap(list<node*> _heap){
    list<node*> ::iterator it;
    it = _heap.begin();
    while (it != _heap.end()){
        printTree(*it);
        it++;
    }
}

///-------------------------------------------------------------

list<node*> createHeap(){
    list<node*> _heap;

    cout << "Cate elemente vor fi adaugate in heap?\n";
    int nr_elem;

    cin >> nr_elem;

    cout << "Care sunt elementele?\n";

    for(int i=0;i<nr_elem;i++){
        int valoare;
        cin >> valoare;
        _heap = insert(_heap,valoare);
    }

    return _heap;
}

int main() {

    vector <list<node*>> heaps;
    int n, q, operatie, multime, element, multime1, multime2;
    cin >> n >> q;

    heaps.resize(n+1);

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

        if(operatie == 1) {
            cin >> multime >> element;
            heaps[multime] = insert(heaps[multime], element);
        }

        if(operatie == 2) {
            cin >> multime;
            heaps[multime] = extractMin(heaps[multime]);
        }

        if(operatie == 3) {
            cin >> multime1 >> multime2;

            heaps[multime2] = unionHeaps(heaps[multime1], heaps[multime2]);
        }

    }

    return 0;
}