#include <iostream>
#include <fstream>
#include <vector>

///#include "pairing_heap.h"
///#include "binomial_heap.h"
///#include "leftist_heap.h"

using namespace std;

struct node_pairing_heap{
    int key;
    node_pairing_heap *child, *sibling;

    node_pairing_heap( int x ) : key( x ), child( NULL ), sibling( NULL ) {}
};
class pairing_heap{

    node_pairing_heap *root;

    node_pairing_heap* merge_heap( node_pairing_heap* H1, node_pairing_heap* H2 ){

        if( H1 == NULL ){
            H1 = H2;
            return H1;
        }
        if( H2 == NULL ) return H1;

        if( H1 -> key < H2 -> key )
            swap( H1, H2 );

        H2 -> sibling = H1 -> child;
        H1 -> child = H2;

        return H1;
    }

    node_pairing_heap* two_pass_merge( node_pairing_heap *_node ){

        if( _node == NULL || _node -> sibling == NULL )
            return _node;

        node_pairing_heap *heap_1, *heap_2, *next_pair;

        heap_1 = _node;
        heap_2 = _node -> sibling;
        next_pair = _node -> sibling -> sibling;

        heap_1 -> sibling = heap_2 -> sibling = NULL;

        return merge_heap( merge_heap( heap_1, heap_2 ), two_pass_merge( next_pair ) );
    }
public:

    pairing_heap() : root( NULL ) {}

    pairing_heap( int _key ){
        root = new node_pairing_heap( _key );
    }

    pairing_heap( node_pairing_heap* _node_pairing_heap ) : root( _node_pairing_heap ) {}

    int top(){
        return root -> key;
    }

    void merge_heap( pairing_heap H ){

        if( root == NULL ){
            root = H.root;
            return;
        }
        if( H.root == NULL ) return;

        if( root -> key < H.root -> key )
            swap( root, H.root );

        H.root -> sibling = root -> child;
        root -> child = H.root;
        H.root = NULL;
    }

    void push( int _key ){
        merge_heap( pairing_heap( _key ) );
    }

    void pop(){

        node_pairing_heap* temp = root;
        root = two_pass_merge( root -> child );

        delete temp;
    }

    void heap_union( pairing_heap &H ){
        merge_heap( H );
        H.root = NULL;
    }
};

int main()
{
    ifstream fin("mergeheap.in");
    ofstream fout("mergeheap.out");

    int N, M;
    fin >> N >> M;


    vector< pairing_heap > list_of_pairing_heap;
    ///vector< binomial_heap > list_of_binomial_heap;
    ///vector< leftist_heap > list_of_leftist_heap;
    for(int i = 0; i <= N; i++){
        pairing_heap temp;
        list_of_pairing_heap.push_back(temp);

        ///binomial_heap temp;
        ///list_of_binomial_heap.push_back(temp);

        ///leftist_heap temp;
        ///list_of_leftist_heap.push_back(temp);
    }

    int task, h, x, h1, h2;
    for( int i = 1; i <= M; ++i ){
        fin >> task;

        if( task == 1 ){
            fin >> h >> x;

            list_of_pairing_heap[h].push( x );
            ///list_of_binomial_heap[h].push( x );
            ///list_of_leftist_heap[h].push( x );
        }
        if( task == 2 ){
            fin >> h;

            fout << list_of_pairing_heap[h].top() << '\n';
            list_of_pairing_heap[h].pop();

            ///fout << list_of_binomial_heap[h].top() << '\n';
            ///list_of_binomial_heap[h].pop();

            ///fout << list_of_leftist_heap[h].top() << '\n';
            ///list_of_leftist_heap[h].pop();
        }
        if( task == 3 ){
            fin >> h1 >> h2;

            list_of_pairing_heap[h1].heap_union( list_of_pairing_heap[h2] );
            ///list_of_binomial_heap[h1].heap_union( list_of_binomial_heap[h2] );
            ///list_of_leftist_heap[h1].heap_union( list_of_leftist_heap[h2] );
        }
    }

    return 0;
}