#include <iostream>
#include<fstream>
using namespace std;
ifstream f("mergeheap.in");
ofstream g("mergeheap.out");
///clasa nodurilor pentru PairingHeap
class Node
{
public:
    Node* next; //child
    int val;
    Node* prev; //sibling
    Node(const int valoare)
    {
        val=valoare;
        next=NULL;
        prev=NULL;
    }
    Node(Node* nod)
    {
        val=nod->val;
        next=nod->next;
        prev=nod->next;
    }
    int getData()
    {
        return val;
    }
};
///clasa pentru operatii
class PairingHeap
{
public:
    Node* radacina;
    PairingHeap() : radacina( NULL ) {}

    PairingHeap( int val ){
        radacina = new Node( val );
    }

    PairingHeap( Node* nod ) : radacina( nod ) {}

    ///pentru operatia 2
    Node* merge(Node* a, Node* b)
    {
    if (a == nullptr)
        return b;
    else if (b == nullptr)
        return a;

    if (a->getData() < b->getData())
        swap(a, b);
    b->prev = a->next;
    a->next = b;
    return a;
}
    Node* mergePairs(Node* node)
    {
        if (node == nullptr || node->prev== nullptr)
            return node;
        Node* prima = node;
        Node* noul = nullptr;
        while (prima != nullptr)
        {
            Node* first = prima;
            Node* second = prima->prev;
            prima = second->prev;
            first->prev = nullptr;
            second->prev = nullptr;
            Node* reuniune = merge(first, second);
            reuniune->prev = noul;
            noul = reuniune;
        }
        return mergePairs(noul);
    }
    int top()
    {
        return radacina->getData();
    }
    void pop()
    {

        Node* nou = radacina;
        if (radacina->next == nullptr)
            radacina = nullptr;
        else radacina = mergePairs(radacina -> next);

        delete nou;
    }
    int extract_max()
    {
        int maxim = top();
        pop();
        return maxim;
    }
    ///pentru operatiile 1 si 3
    void insert(const int& value)
    {
        Node* nod = new Node(value);
        radacina = merge(radacina, nod);
    }
    void merge(PairingHeap& other) {
        radacina = merge(radacina, other.radacina);
        other.radacina = nullptr;
    }
};
int main()
{
    int N, Q;
    f >> N >> Q;
    PairingHeap heap[N];
    for (int i = 0; i < Q; i++)
    {
        int op, m, x, y;
        f >> op;
        switch (op)
        {
            case 1:
                f >> m >> x;
                heap[m].insert(x);
                break;

            case 2:
                f >> m;
                g << heap[m].extract_max() <<"gata"<< endl;
                break;

            case 3:
                f >> x >> y;
                heap[x].merge(heap[y]);
                break;
        }
    }

    return 0;
}