#include <fstream>
#include <vector>

using namespace std;

ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");

template<typename type>
class pairingHeap{
    int key;
    pairingHeap<type>* child;
    pairingHeap<type>* next;
public:
    pairingHeap(){
        child = NULL;
        next = NULL;
    }

    pairingHeap(type key, pairingHeap<type>* child, pairingHeap<type>* next){
    this->key = key;
    this->child = child;
    this->next = next;
    }

    pairingHeap<type>* merge(pairingHeap<type>*);
    pairingHeap<type>* insert(type);
    pairingHeap<type>* twoPassMerge(pairingHeap<type>*);
    type removeMax();
};

template<typename type>
pairingHeap<type>* pairingHeap<type>::merge(pairingHeap<type>* temp){
    if(this == NULL)
        return temp;
    if(temp == NULL)
        return this;
    if(this->key > temp->key){
        temp->next = this->child;
        this->child = temp;
        return this;
    }
    this->next = temp->child;
    temp->child = next;
    return temp;
}

template<typename type>
pairingHeap<type>* pairingHeap<type>::insert(type key){
    return this->merge(new pairingHeap<type>(key, NULL, NULL));
}

// will be used for "rebuilding" the heap without the root (deleting the root node)
template<typename type>
pairingHeap<type>* pairingHeap<type>::twoPassMerge(pairingHeap<type>* node){
    if(node == NULL)
        return NULL;
    if(node->next == NULL)
        return node;
    pairingHeap<type>* temp1 = node;
    pairingHeap<type>* temp2 = node->next;

    // next node that i want to call the function for, i will not be able to just call twoPassMerge(node->next->next)
    // as node->next and node->next->next are going to become NULL;
    pairingHeap<type>* nextNode = node->next->next;

    temp1->next = NULL; // they are "binded" to the old tree, that will generate problems.
    temp2->next = NULL;
    return (temp1->merge(temp2))->merge(twoPassMerge((nextNode)));
}

template<typename type>
type pairingHeap<type>::removeMax(){
    if(this == NULL)
        return 0; //basic value if somebody tries to remove the max of an empty heap
    type temp = this->key;
    twoPassMerge(this->child);
    return temp;
}

int main()
{
    int n, q, op, m, a, b, x;
	vector< pairingHeap<int>* > heaps;
	fin >> n >> q;
	heaps.resize(n+5);
	for(int i = 0; i < q; ++i){
		fin >> op;
		if(op == 1){
			fin >> m >> x;
			heaps[m] = heaps[m]->insert(x);
			continue;
		}
		if(op == 2){
			fin >> m;
			fout << heaps[m]->removeMax() << '\n';
			continue;
		}
		if(op == 3){
			fin >> a >> b;
			heaps[a]->merge(heaps[b]);
			heaps[b] = NULL;
		}
	}
}