#include <iostream>
#include <algorithm>
#include <fstream>


std::ifstream in("mergeheap.in");
std::ofstream out("mergeheap.out");



class RankPairingHeap {

public:

    RankPairingHeap() : root(nullptr) {}

    void insert(int cheie) {
        Node* node = new Node(cheie);
        root = merge(root, node);
    }

    int pop() {

        int key = root->key;
        Node* new_root = nullptr;

        // parcurgere 

        for (Node* child = root->left; child != nullptr; ) {

            Node* next = child->right;
            child->right = nullptr;
            new_root = merge(new_root, child);
            child = next;
        }



        delete root;
        root = new_root;

        return key;
    }

    bool empty() const {
        return root == nullptr;
    }

    RankPairingHeap mergeThem(RankPairingHeap* heap1, RankPairingHeap* heap2)
    {
        Node* new_root = merge(heap1->root, heap2->root);
        RankPairingHeap merged_heap;
        merged_heap.root = new_root;
        return merged_heap;
    }

private:
    
    struct Node {
        Node(int key) : key(key), left(nullptr), right(nullptr) {}

        int key;
        Node* left;
        Node* right;
    };

    Node* merge(Node* a, Node* b) {

        if (!a) return b;
        if (!b) return a;

        if (a->key > b->key) 
        {
            b->right = a->left;
            a->left = b;

            return a;
        }
        else 
        {
            a->right = b->left;
            b->left = a;

            return b;
        }
    }

    Node* root;

public:
    Node* getRoot()
    {
        return root;
    }
};

void insertInHeap(RankPairingHeap heap[])
{
    int m, x;
    in >> m >> x;

    heap[m].insert(x);
}

void printdinHeap(RankPairingHeap heap[])
{
    int m;
    in >> m;

    out << heap[m].pop() << std::endl;
}

void mergeHeaps(RankPairingHeap heap[])
{
    int a, b;
    in >> a >> b;

    heap[a] = heap[a].mergeThem(&heap[a], &heap[b]);

}


int main()
{
  int n, q;

    in >> n >> q;
    
    RankPairingHeap* heaps = new RankPairingHeap[n];

    for (int i = 0; i < q; i++)
    {
        int op;
        in >> op;

        switch (op)
        {
        case 1:
            insertInHeap(heaps);
            break;
        case 2:
            printdinHeap(heaps);
            break;
        case 3:
            mergeHeaps(heaps);
        }

    }

}