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

using namespace std;

std::ifstream cin("mergeheap.in");
std::ofstream cout("mergeheap.out");

class node{
    int val;
    node* copil, *frate;

public:
    int getVal() const {
        return val;
    }

    void setVal(int val) {
        node::val = val;
    }

    node *getCopil() const {
        return copil;
    }

    void setCopil(node *copil) {
        node::copil = copil;
    }

    node *getFrate() const {
        return frate;
    }

    void setFrate(node *frate) {
        node::frate = frate;
    }

    node(int v):val(v),copil(nullptr),frate(nullptr){}
    void addcopil(node *nd){
        if(nd== nullptr)return;
        node* aux = copil;
        while(aux->frate!= nullptr){
            aux= aux->frate;
        }
        aux =aux->frate;
        aux = nd;
    }
};
class pheap{
    node *root;
public:
    pheap(){root= nullptr;}
    void push(int val){
        if(root==nullptr){
            root = new node(val);
            return;
        }
        root->addcopil(new node(val));
    }
    void merge(pheap B){
        if(B.root == nullptr)return;
        if(root == nullptr){
            root = B.root;
            B.root = nullptr;
            return;
        }
        if(B.root->getVal()<root->getVal()){
            root->addcopil(B.root);
            return;
        }
        else {
            B.root->addcopil(root);
            root = B.root;
            B.root = nullptr;
        }
    }
    static node * merge_pairs(node * nod){
        if(nod == nullptr || nod->getFrate() == nullptr)return nod;
        pheap p1,p2,p3;
        node *urm;
        p1.root = nod;
        p2.root = nod->getFrate();
        urm = nod->getFrate()->getFrate();
        p1.merge(p2);
        p3.root = merge_pairs(urm);
        p1.merge(p3);
        return p1.root;
    }
    int toppop() {
        int rez = root->getVal();
        root = merge_pairs(root->getCopil());
        return rez;
    }
};

int main() {
    int n,q;
    cin>>n>>q;
    pheap *h = new pheap[n];
    for(int i=0;i<q;i++){
        int querry;
        cin>>querry;
        switch(querry){
            case 1:{
                int m,x;
                cin>>m>>x;
                h[m-1].push(x);
                break;
            }
            case 2:{
                int m;
                cin>>m;
                cout<<h[m-1].toppop()<<"\n";
                break;
            }
            case 3:{
                int a,b;
                cin>>a>>b;
                h[a-1].merge(h[b-1]);
                break;
            }
            default:{}
        }
    }
    return 0;
}