#include <bits/stdc++.h>

using namespace std;
typedef struct heap heap;
typedef heap* pheap;
mt19937 G;
uniform_int_distribution<int> u(1 , 100);
struct heap{
    int mx = INT_MIN;
    pheap l = nullptr;
    pheap r = nullptr;
};
pheap merge(pheap x , pheap y){
    if(!x || !y)
        return x ? x : y;
    if(y->mx > x->mx)
        swap(x , y);
    if(u(G) & 1){
        swap(x->l , x->r);
    }
    x->l = merge(x->l , y);
    return x;
}
void insert(pheap &h , int x){
    pheap nh = new heap;
    nh->mx = x;
    h = merge(h , nh);
}
void remove(pheap &h){
    h = merge(h->l , h->r);
}
int main()
{
    G.seed(time(NULL));
    ifstream fin("mergeheap.in");
    ofstream fout("mergeheap.out");
    int n , q;
    fin >> n >> q;
    vector<pheap> h(n + 1);
    while(q --){
        int a , b , c;
        fin >> a >> b;
        if(a == 1){
            fin >> c;
            insert(h[b] , c);
        }else{
            if(a == 2){
                fout << h[b]->mx << '\n';
                remove(h[b]);
            }else{
                fin >> c;
                h[b] = merge(h[b] , h[c]);
                h[c] = nullptr;
            }
        }
    }
    return 0;
}