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

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

struct HeapNode
{
	int key;
	HeapNode *leftChild;
	HeapNode *nextSibling;

	void addChild(HeapNode* node)
	{
		if (leftChild == NULL)leftChild = node;
		else
        {
			node->nextSibling = leftChild;
			leftChild = node;
		}
	}

};

HeapNode* Merge(HeapNode* A, HeapNode* B)
{
	if (A == NULL)return B;
	if (B == NULL)return A;

	if (A->key > B->key)
	{
		A->addChild(B);
		return A;
	}
	else
    {
		B->addChild(A);
		return B;
	}
}

HeapNode* Delete(HeapNode* node)
{
	if (node == NULL || node->nextSibling == NULL)
		return node;
	else
	{
		HeapNode* A = node;
		HeapNode* B = node->nextSibling;
		HeapNode* newNode = node->nextSibling->nextSibling;

		A->nextSibling = NULL;
		B->nextSibling = NULL;

		return Merge(Merge(A, B), Delete(newNode));

	}
}

HeapNode* Insert(HeapNode* node, int key)
{
	HeapNode* temporary = new HeapNode();
	temporary->key = key;
	return Merge(node, temporary);
}

class PairingHeap
{
public:
	HeapNode* root;
	PairingHeap():root(NULL){}
	void Insert(int key){root = ::Insert(root, key);}
	void Join(PairingHeap& other){root = Merge(root, other.root); other.root = NULL;}
	void Delete(){g<<root->key<< '\n'; root = ::Delete(root->leftChild);}
};

int main()
{
	int n, q, op, m, x, b;
	f>>n>>q;
	vector<PairingHeap> ph(n + 1);

	for(int i=0;i<q;i++)
	{
		f>>op>>m;
		switch (op)
		{
            case 1:
            {
                f>> x;
                ph[m].Insert(x);
                break;
            }
            case 2:
            {
                ph[m].Delete();
                break;
            }
            case 3:
            {
                f>> b;
                ph[m].Join(ph[b]);
                break;
            }
		}
	}
	return 0;
}