#include <fstream>
#include <vector>
#include <climits>
#include <cmath>

using namespace std;



class Node
{
	friend class FibonacciHeap;
	Node(int value): value(value), height(0), parent(nullptr), left(nullptr), right(nullptr) {}
private:
	int value;
	int height;
	vector<Node*> children;
	Node* parent;
	Node* left;
	Node* right;
};

class FibonacciHeap
{
public:
	FibonacciHeap() : max(nullptr), node_count(0) {}
	void insert(int);
	void insert(Node*);
	void merge(FibonacciHeap&);
	int getMax();
	void deleteMax();
private:
	Node* max;

	int node_count;
};

void FibonacciHeap::insert(int value)
{
	if (!max)
	{
		max = new Node(value);
		max->left = max;
		max->right = max;
	}
	else
	{
		Node* right_of_max = max->right;
		Node* new_node = new Node(value);

		max->right = new_node;
		right_of_max->left = new_node;
		new_node->left = max;
		new_node->right = right_of_max;

		if (new_node->value > max->value)
			max = new_node;
	}
	node_count++;

}

void FibonacciHeap::insert(Node* n)
{
	if (!max)
	{
		max = n;
		max->left = n;
		max->right = n;
	}
	else
	{
		Node* right_of_max = max->right;
		Node* new_node = n;

		max->right = new_node;
		right_of_max->left = new_node;
		new_node->left = max;
		new_node->right = right_of_max;

		if (new_node->value > max->value)
			max = new_node;
	}
	node_count++;

}

void FibonacciHeap::merge(FibonacciHeap& fh)
{
	if (!fh.max)
		return;
	if (!max)
	{
		*this = fh;
		return;
	}
	node_count += fh.node_count;
	fh.node_count = 0;
	Node* this_begin = max->right;			// list1=(x1 x2 x3 x4)    list2=(y1 y2 y3 y4), assume x4 = max and y1 = fh.max
	Node* fh_end = fh.max->left;			// save pointers to x1 (first list begin), y4(second list end)
			
	max->right = fh.max;					// link x4 to y1
	fh.max->left = max;
	this_begin->left = fh_end;				// link x1 to y4
	fh_end->right = this_begin;

	if (fh.max->value > this->max->value)
		this->max = fh.max;
	fh.max = nullptr;


}

int FibonacciHeap::getMax()
{
	return max->value;
}

void FibonacciHeap::deleteMax()
{
	if (!max)		// empty
		return;
	if (max->left == max && max->children.size() == 0)		// 1 node
	{
		delete max;
		max = nullptr;
		node_count = 0;
		return;
	}
	for (auto subtree : max->children)
		this->insert(subtree);
	max->right->left = max->left;
	max->left->right = max->right;
	Node* deleted_max_address = max;
	max = max->right;
	delete deleted_max_address;
	node_count--;

	vector<Node*> order_distribution(log2(node_count) + 1, nullptr);		// log2(n) max possible number of trees
	order_distribution[max->height] = max;
	Node* list_iterator = max->right;
	Node* end_point = max;
	while(list_iterator != end_point)
	{
		Node* new_tree = list_iterator;
		while(order_distribution[new_tree->height] != nullptr)
		{
			Node* other_root = order_distribution[new_tree->height];
			if (new_tree->value >= other_root->value)
			{

				new_tree->children.push_back(other_root);
				other_root->parent = new_tree;
				order_distribution[new_tree->height] = nullptr;
				new_tree->height++;
			}
			else
			{

				other_root->children.push_back(new_tree);
				new_tree->parent = other_root;
				order_distribution[new_tree->height] = nullptr;
				other_root->height++;

				new_tree = other_root;
			}
		}
		order_distribution[new_tree->height] = new_tree;
		list_iterator = list_iterator->right;
	}

	max = nullptr;
	for (auto rebuilt_root : order_distribution)
		if (rebuilt_root)
		{
			this->insert(rebuilt_root);
			if (rebuilt_root->value > max->value)
				max = rebuilt_root;
		}

}

int main()
{
	ifstream f("mergeheap.in");
	ofstream g("mergeheap.out");
	int tip_operatie, nr_operatii, nr_heapuri;
	f >> nr_heapuri >> nr_operatii;
	int v1, v2;
	vector<FibonacciHeap> heapuri(nr_heapuri + 1);
	for (int i = 0; i < nr_operatii; i++)
	{
		f >> tip_operatie;
		if (tip_operatie == 1)
		{
			f >> v1 >> v2;
			heapuri[v1].insert(v2);
		}
		else if (tip_operatie == 2)
		{
			f >> v1;
			g << heapuri[v1].getMax() << "\n";
			heapuri[v1].deleteMax();
		}
		else if (tip_operatie == 3)
		{
			f >> v1 >> v2;
			heapuri[v1].merge(heapuri[v2]);
		}

	}





}