#include <iostream>
#include <vector>
#include <fstream>
#include <unordered_map>
#include <queue>
using namespace std;

const int NMAX = 105;

struct nod{
    int key;
    nod *left = nullptr, *right = nullptr;
    int rrank;
};

class rheap{
    nod* root = nullptr;

public:
    rheap(){
    }
    ~rheap(){
    }
    nod* getroot()const{
        return root;
    }
    void setnroot(){
        root = nullptr;
    }
    void setroot(nod* nroot){
        root = nroot;
    }
    static nod* snmerge(nod* a, nod* b){
        if(a == nullptr)
            return b;
        if(b == nullptr)
            return a;
        if(a -> key > b -> key){
            b -> right = a -> left;
            a -> left = b;
            a -> rrank++;
            return a;
        }
        else{
            a -> right = b -> left;
            b -> left = a;
            b -> rrank++;
            return b;
        }
    }

    void nmerge(nod* b){
        if(root == nullptr){
            root = b;
            return;
        }
        if(b == nullptr)
            return;
        if(root -> key > b -> key){
            b -> right = root -> left;
            root -> left = b;
            root -> rrank++;
        }
        else{
            root -> right = b -> left;
            b -> left = root;
            b -> rrank++;
            root = b;
        }
    }
    int npop(){
        int afr = root -> key;
        /*unordered_map<int, vector<nod*>> rmap;
        nod* aux = root -> left;
        int mrank = -1;
        while(aux != nullptr){
            rmap[aux->rrank].push_back(aux);
            mrank = max(mrank, aux -> rrank);
            aux = aux -> right;
        }
        while(rmap.size() > 1){
            nod* a1, *a2, *a3;
            a1 = nullptr;
            a2 = nullptr;
            a3 = nullptr;
            for(int i = 0; i <= mrank; i++){
                for(int j = 0; j < rmap[i].size(); j++){
                    if(a1 == nullptr){
                        a1 = rmap[i][j];
                        rmap[i].erase(rmap[i].begin() + j);
                        j--;
                    }
                    else if(a2 == nullptr){
                        a2 = rmap[i][j];
                        rmap[i].erase(rmap[i].begin() + j);
                        j--;
                        a3 = rheap::snmerge(a1, a2);
                        rmap[a3 -> rrank].push_back(a3);
                        mrank = max(mrank, a3 -> rrank);
                        a1 = nullptr;
                        a2 = nullptr;
                    }
                }
            }
        }
        for(int i = 0; i <= mrank; i++){
            if(rmap[i].size() == 1){
                root = rmap[i][0];
            }
        }*/
        queue <nod*> cd;
        nod *aux = root -> left;
        cd.push(aux);
        if(aux == nullptr){
            root = cd.front();
            cd.pop();
            return afr;
        }
        aux = aux -> right;
        while(aux != nullptr){
            cd.push(aux);
            aux = aux -> right;
        }
        nod *a1, *a2;
        while(cd.size() > 1){
            a1 = cd.front();
            cd.pop();
            a2 = cd.front();
            cd.pop();
            aux = rheap::snmerge(a1, a2);
            cd.push(aux);
        }
        root = cd.front();
        return afr;
    }
    void npush(int val){
        nod *aux = new nod;
        aux -> key = val;
        aux -> rrank = 0;
        this -> nmerge(aux);
        //root = rheap::snmerge(root, aux);
    }
};

int main()
{
    int n, q, op;
    rheap prnc[NMAX]; ///heaps
    ifstream f("mergeheap.in");
    ofstream g("mergeheap.out");
    int m, x, a, b;
    f >> n >> q;
    while(q){
        f >> op;
        switch(op){
        case 1:
            //cout << "!";
            f >> m >> x;
            prnc[m].npush(x);
            //cout << "!";
            break;
        case 2:
            //cout << "@";
            f >> m;
            //g << prnc[m].get_min() << "\n";
            g << prnc[m].npop() << "\n";
            //cout << "@";
            break;
        case 3:
            //cout << "#";
            f>> a >> b;
            prnc[a].nmerge(prnc[b].getroot());
            prnc[b].setnroot();
            //cout << "#";
            break;
        }
        ///DEBUG
        /*
        cout << "\n\n";
        for(int i = 1; i <= n; i++){
            cout << i << "\n\n";
            nod* aux = prnc[i].getroot();
            if(aux != nullptr)
                while(aux){
                    nod *aux2 = aux;
                    while(aux){
                        cout << aux -> key << " ";
                        aux = aux -> right;
                    }
                    cout << "\n----\n";
                    aux = aux2 -> left;
                }
            else
                cout << "NONE";
            cout << "\n\n";
        }
        cout<<"\n\n";
        */
        ///
        q--;
    }
}