#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <stdio.h>
#include <ctype.h>

using namespace std;

///ifstream in("mergeheap.in");
ofstream out("mergeheap.out");

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

int n,m,op,a,b;

struct Nod
{
    int val,grad;
    Nod *fiu,*frate,*tata;
};

Nod* New(int val)
{
    Nod *acm = new Nod;
    acm->val = val;
    acm->grad = 0;
    acm->fiu = acm->frate = acm->tata = NULL;
    return acm;
}

Nod* Link(Nod *a, Nod *b)
{
    b->tata = a;
    b->frate = a->fiu;
    a->fiu = b;
    a->grad++;

    return a;
}

vector<Nod*> Union(vector<Nod*> a,vector<Nod*> b)
{
    vector<Nod*> nou;
    vector<Nod*>::iterator i,j;
    i = a.begin();
    j = b.begin();
    while (i != a.end() && j != b.end())
    {
        if ((*i)->grad <= (*j)->grad)
        {
            nou.push_back(*i);
            i++;
        }
        else
        {
            nou.push_back(*j);
            j++;
        }
    }
    while (i != a.end())
    {
        nou.push_back(*i);
        i++;
    }
    while (j != b.end())
    {
        nou.push_back(*j);
        j++;
    }
    return nou;
}

vector<Nod*> Ajustare(vector<Nod*> heap)
{
    if (heap.size() <= 1) return heap;

    vector<Nod*>::iterator last,x,nxt;
    last = x = nxt = heap.begin();

    if (heap.size() == 2)
    {
        x = heap.begin() + 1;
        nxt = heap.end();
    }
    else
    {
        x = heap.begin() + 1;
        nxt = heap.begin() + 2;
    }


    if (m == 4)
    {
        for (auto y:heap) cout << y->grad << " ";
        cout << "\n";
    }
    while (last != heap.end())
    {
        ///if (m == 4 && (*x)->grad == 2 &&  (*last)->grad == 2);
        ///if (m == 4 && (*x)->grad == 2 &&  (*last)->grad == 2) cout << (nxt != heap.end());
        if (x == heap.end() && last != heap.end())
        {
            last++;
        }
        else if ((*last)->grad < (*x)->grad)
        {
            x++;
            last++;
            if (nxt != heap.end()) nxt++;
        }
        else if (nxt != heap.end() && (*last)->grad == (*x)->grad && (*x)->grad == (*nxt)->grad)
        {
            last++;
            x++;
            nxt++;
        }
        else if ((*last)->grad == (*x)->grad)
        {
            if ((*x)->val > (*last)->val) swap(*x,*last);
            *last = Link(*last, *x);
            x = heap.erase(x);
            nxt = x;
            if (nxt != heap.end()) nxt++;
        }
    }
    return heap;
}

Nod* Maxi(vector<Nod*> heap)
{
    vector<Nod*>::iterator it = heap.begin();

    Nod* mi = *it;
    while (it != heap.end())
    {
        if ((*it)->val > mi->val)
        {
            mi = *it;
        }
        it++;
    }
    return mi;
}

vector<Nod*> Extrage(Nod* cap)
{
    vector<Nod*> nw;
    Nod *tmp = cap->fiu,*nxt;

    while (tmp != NULL)
    {
        nxt = tmp;
        tmp = tmp->frate;
        nxt->frate = NULL;
        nw.push_back(nxt);
    }
    reverse(nw.begin(), nw.end());
    return nw;
}

vector<Nod*> Sterge_max(vector<Nod*> heap)
{
    vector<Nod*> nw;
    Nod* maxi = Maxi(heap);
    out << maxi->val << "\n";
    vector<Nod*>::iterator it = heap.begin();

    while (it != heap.end())
    {
        if (*it != maxi) nw.push_back(*it);
        it++;
    }
    vector<Nod*> lol;
    lol = Extrage(maxi);

    heap = Union(nw, lol);
    heap = Ajustare(heap);
    return heap;

}

vector<Nod*> Insert(int val,vector<Nod*> heap)
{
    Nod *temp = New(val);
    vector<Nod*> nw;
    nw.push_back(temp);
    heap = Union(heap, nw);
    heap = Ajustare(heap);
    return heap;
}

vector<Nod*> multimi[105];

int main()
{
    InParser in("mergeheap.in");
    int cnt = 0;
    in >> n >> m;
    while (m--)
    {
        in >> op;
        cnt++;
        if (op == 1)
        {
            in >> a >> b;
            multimi[a] = Insert(b, multimi[a]);
        }
        else if (op == 2)
        {
            in >> a;
            multimi[a] = Sterge_max(multimi[a]);
        }
        else
        {
            in >> a >> b;
            multimi[a] = Union(multimi[a], multimi[b]);

            multimi[a] = Ajustare(multimi[a]);
            multimi[b].clear();
        }

    }
    return 0;
}