#include <bits/stdc++.h>
using namespace std;
ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");
class Node
{
public:
    int key;
    Node **forward;
    Node(int, int);
};

Node::Node(int key, int level)
{
    this->key = key;
    forward = new Node*[level+1];
    memset(forward, 0, sizeof(Node*)*(level+1));
};

class SkipList
{
    int MAXLVL;
    float P;
    int level;
    Node *header;
public:
    SkipList();
    SkipList(int, float);
    int randomLevel();
    Node* createNode(int, int);
    void insertElement(int);
    void deleteElement(int);
    bool searchElement(int);
    void displayList();
    int maxElement();
    vector<int> elements();
    void mergeSet(SkipList&);
};
SkipList::SkipList()
{
    MAXLVL=0;P=0;
    this->MAXLVL = MAXLVL;
    this->P = P;
    level = 0;
    header = new Node(-1, MAXLVL);
};
SkipList::SkipList(int MAXLVL, float P)
{
    this->MAXLVL = MAXLVL;
    this->P = P;
    level = 0;
    header = new Node(-1, MAXLVL);
};

int SkipList::randomLevel()
{
    float r = (float)rand()/RAND_MAX;
    int lvl = 0;
    while(r < P && lvl < MAXLVL)
    {
        lvl++;
        r = (float)rand()/RAND_MAX;
    }
    return lvl;
};

Node* SkipList::createNode(int key, int level)
{
    Node *n = new Node(key, level);
    return n;
};

void SkipList::insertElement(int key)
{
    Node *current = header;
    Node *update[MAXLVL+1];
    memset(update, 0, sizeof(Node*)*(MAXLVL+1));
    for(int i = level; i >= 0; i--)
    {
        while(current->forward[i] != NULL &&
              current->forward[i]->key < key)
            current = current->forward[i];
        update[i] = current;
    }
    current = current->forward[0];
    if (current == NULL || current->key != key)
    {
        int rlevel = randomLevel();
        if(rlevel > level)
        {
            for(int i=level+1;i<rlevel+1;i++)
                update[i] = header;
            level = rlevel;
        }
        Node* n = createNode(key, rlevel);
        for(int i=0;i<=rlevel;i++)
        {
            n->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = n;
        }
    }
};

void SkipList::deleteElement(int key)
{
    Node *current = header;
    Node *update[MAXLVL+1];
    memset(update, 0, sizeof(Node*)*(MAXLVL+1));
    for(int i = level; i >= 0; i--)
    {
        while(current->forward[i] != NULL  && current->forward[i]->key < key)
            current = current->forward[i];
        update[i] = current;
    }
    current = current->forward[0];
    if(current != NULL and current->key == key)
    {
        for(int i=0;i<=level;i++)
        {
            if(update[i]->forward[i] != current) break;
            update[i]->forward[i] = current->forward[i];
        }

        while(level>0 && header->forward[level] == 0)
            level--;
    }
};

bool SkipList::searchElement(int key)
{
    Node *current = header;
    for(int i = level; i >= 0; i--)
    {
        while(current->forward[i] && current->forward[i]->key < key)
            current = current->forward[i];

    }
    current = current->forward[0];
    return current and current->key == key;
};

int SkipList::maxElement()
{
    Node *current = header;
    while(current->forward[0]) current = current->forward[0];
    return current->key;
};

vector<int> SkipList::elements()
{
    vector<int> v;
    Node *node = header->forward[0];
    while(node != NULL)
    {
        v.push_back(node->key);
        node = node->forward[0];
    }
    return v;
};

void SkipList::mergeSet(SkipList &lst)
{
    vector<int> v=lst.elements();
    for(auto x:v)
    {
        this->insertElement(x);
        lst.deleteElement(x);
    }
};

// Display skip list level wise
void SkipList::displayList()
{
    cout<<"\n*****Skip List*****"<<"\n";
    for(int i=0;i<=level;i++)
    {
        Node *node = header->forward[i];
        cout<<"Level "<<i<<": ";
        while(node != NULL)
        {
            cout<<node->key<<" ";
            node = node->forward[i];
        }
        cout<<"\n";
    }
};

int main()
{
    srand((unsigned)time(0));
    vector<SkipList>lst(105);
    int n,q,op,m,x,a,b;
    fin>>n>>q;
    for(int i=1;i<=n;i++) {SkipList sl(20,0.5);lst[i]=sl;}
    while(q--)
    {
        fin>>op;
        switch(op)
        {
        case 1:
            fin>>m>>x;
            lst[m].insertElement(x);
            break;
        case 2:
            fin>>m;
            x=lst[m].maxElement();
            fout<<x<<"\n";
            lst[m].deleteElement(x);
            break;
        default:
            fin>>a>>b;
            lst[a].mergeSet(lst[b]);
            break;
        }
    }
}