#include<iostream>
#include<random>
#include<ctime>
using namespace std;

mt19937 rng(time(nullptr));

struct nod
{
    int v; nod* st; nod* dr;
    nod(int x) : v(x), st(0), dr(0){}
};

nod* join(nod* a, nod* b)
{
    if(!a || !b)
        return a ? a : b;
    if(a->v < b->v) swap(a, b);
    if(rng() & 1) swap(a->st, a->dr);
    a->st = join(a->st, b); return a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    freopen("mergeheap.in", "r", stdin);
    freopen("mergeheap.out", "w", stdout);

    int n, q, t, a, b; cin >> n >> q;
    nod* roots[n + 1] = {0};
    for(int i = 1; i <= n ; i++) if(roots[i] != nullptr) exit(1);
    for(int i = 1; i <= q ; i++)
        {
            cin >> t;
            if(t == 1)
                {
                    cin >> a >> b;
                    roots[a] = join(roots[a], new nod(b));
                }

            else if(t == 2)
                {
                    cin >> a;
                    cout << roots[a]->v << '\n';
                    roots[a] = join(roots[a]->st, roots[a]->dr);
                }

            else
                {
                    cin >> a >> b;
                    roots[a] = join(roots[a], roots[b]); roots[b] = 0;
                }
        }
}