#include <iostream>
#include <fstream>
using namespace std;

ifstream f("mergeheap.in");
ofstream g("mergeheap.out");

struct Node{
    int x;
    Node* fiu;
    Node* frate;

    Node(int x){
        this->x = x;
        this->fiu = NULL;
        this->frate = NULL;
    }
};

class Heap{
    Node* radacina;

public:
    Heap() {this->radacina = NULL;}

    void extrageMax();
    void insereaza(int x);
    void merge(Node*);
    Node* merge(Node*, Node*);
    void merge(Heap*);
    Node* metoda_2_pass(Node*);
};

void Heap::merge(Node* rad){
    if(this->radacina == NULL)
        this->radacina = rad;
    else
        if(rad != NULL){
            if(this->radacina->x < rad->x)
                swap(this->radacina, rad);
            rad->frate = this->radacina->fiu;
            this->radacina->fiu = rad;
        }
}

Node* Heap::merge(Node* r1, Node* r2){
    if(r1 == NULL){
        r1 = r2;
        return r1;
    }
    if(r2 == NULL)
        return r1;

    if(r1->x < r2->x)
        swap(r1, r2);

    r2->frate = r1->fiu;
    r1->fiu = r2;
    return r1;
}

void Heap::merge(Heap* h){
    merge(h->radacina);
    h->radacina = NULL;
}

void Heap::insereaza(int x){
    if(this->radacina == NULL)
        this->radacina = new Node(x);
    else{
        merge(new Node(x));
    }
}

Node* Heap::metoda_2_pass(Node* nod){
    if(nod == NULL || nod->frate == NULL)
        return nod;
    else{
        Node* fr = nod->frate;
        Node* fr2 = nod->frate->frate;
        nod->frate = NULL;
        fr->frate = NULL;
        return merge(merge(nod, fr), metoda_2_pass(fr2));
    }
}

void Heap::extrageMax(){
    g << this->radacina->x;
    Node* copie = this->radacina;
    this->radacina = metoda_2_pass(this->radacina->fiu);
    delete copie;
}

int main(){
    Heap h[102];

    int n, nrOp, op, poz, x, poz2;
    f >> n >> nrOp;

    for(int i = 0; i < nrOp; i++){
        f >> op;
        switch(op){
            case 1:{
                f >> poz >> x;
                h[poz].insereaza(x);
                break;
            }
            case 2:{
                f >> poz;
                h[poz].extrageMax();
                g << "\n";
                break;
            }
            case 3:{
                f >> poz >> poz2;
                h[poz].merge(&h[poz2]);
                break;
            }
        }
    }
    f.close();
    g.close();
    return 0;
}