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

using namespace std;

class Node{
public:
    int value;
    Node* parent;
    Node* left;
    Node* right;
    Node* child;
    bool marked;
    int degree;
    bool seen;
    Node(int val);
    Node();
    friend ostream& operator <<(ostream& out, const Node&);
    Node& operator =(const Node&);
};
ostream& operator <<(ostream& out, const Node& n){
    cout<<"============NODE============";
    cout<<"VALUE: "<<n.value<<" ";
    if(n.parent != nullptr)
        cout<<"PARENT: "<<n.parent->value<<" ";
    if(n.right != nullptr)
        cout<<"RIGHT: "<<n.right->value<<" ";
    if(n.child != nullptr)
        cout<<"CHILD: "<<n.child->value<<" ";
    if(n.left != nullptr)
        cout<<"LEFT: "<<n.left->value<<endl;

    return out;
}
Node::Node(int val){
    this->value = val;
    this->parent = nullptr;
    this->child = nullptr;
    this->right = this;
    this->left = this;
    this->marked = false;
    this->seen = false;
    this->degree = 0;
}
Node::Node(){
    this->value = 0;
    this->parent = nullptr;
    this->child = nullptr;
    this->right = this;
    this->left = this;
    this->marked = false;
    this->seen = false;
    this->degree = 0;
}
Node& Node::operator=(const Node& node){
    if(this != &node){
        this->value = node.value;
        this->parent = node.parent;
        this->left = node.left;
        this->right = node.right;
        this->child = node.child;
        this->marked = node.marked;
        this->degree = node.degree;
        this->seen = node.seen;
    }
    return *this;
}

class FibonacciHeap{
    Node* maxNode;
    Node* head;
    int size;
public:
    FibonacciHeap(){ this->maxNode = nullptr; this->head = nullptr; this->size = 0; }
    FibonacciHeap(int size, Node* max, Node* H){
        this->size = size;
        this->maxNode = max;
        this->head = H;
    }
    void insert(int val){
        Node* n = new Node(val);
        if(this->maxNode == nullptr){
            this->maxNode = n;
            this->head = n;
        } else {
            Node* last = this->head->left;

            n->right = head;
            n->left = last;
            last->right = n;
            head->left = n;

            if(this->maxNode->value < n->value) this->maxNode = n;
        }
        this->size+=1;
    }

    FibonacciHeap& heapUnion(FibonacciHeap& heap2) {
        if(heap2.maxNode->value > this->maxNode->value){
            this->maxNode = heap2.maxNode;
        }

        Node* last = heap2.head->left;
        Node* first = this->head;
        Node* lastOfFirst = this->head->left;
        Node* firstOfSecond = heap2.head;

        firstOfSecond->left = lastOfFirst;
        last->right = first;
        lastOfFirst->right = firstOfSecond;
        first->left = last;

        this->size += heap2.size;

        return *this;
    }

    void extractToRootList(Node* node){
        if(this->head == nullptr){
            this->head = node;
        }

        Node* last = this->head->left;

        node->right = head;
        node->left = last;
        head->left = node;
        last->right = node;

        node->parent = nullptr;
    }
    void extractChildrenToRootList(Node* child){
        Node* lastChild = child->left;
        Node* last = this->head->left;

        lastChild->right = head;
        child->left = last;
        head->left = lastChild;
        last->right = child;

        child->parent->child = nullptr;
    }

    void loop(Node* node, vector<Node*>& A){
        int d;
        Node* next = node->right;
        d = node->degree;
        while(A[d] != nullptr){
            Node* y = A[d];
            if(node->value < y->value) {
                Node *aux = node;
                node = y;
                y = aux;
            }
            this->link(this->head, y, node);
            A[d] = nullptr;
            d = d + 1;
        }
        A[d] = node;
        if(!next->seen){
            next->seen = true;
            this->loop(next, A);
            next->seen = false;
        }
    }

    void consolidate(Node* H){
        vector<Node*> A(this->size);
        for(int i=0; i<this->size; i++){
            A.push_back(nullptr);
        }

        this->head->seen = true;
        this->loop(this->head, A);
        this->head->seen = false;

        this->maxNode = nullptr;
        this->head = nullptr;
        for(int i=0; i<A.size(); i++){
            if(A[i] != nullptr){
                this->extractToRootList(A[i]);
                if(this->maxNode == nullptr || A[i]->value > this->maxNode->value){
                    this->maxNode = A[i];
                }
            }
        }
    }
    void link(Node* node, Node* y, Node* x){
        Node* left = y->left;
        Node* right = y->right;
        left->right = right;
        right->left = left;

        if(x->child != nullptr){
            Node* child = x->child;
            Node* last = child->left;
            right = child;
            left = last;
            last->right = y;
            child->left = y;
            y->parent = x;
        } else {
            x->child = y;
            y->parent = x;
            left = y;
            right = y;
        }
        x->degree++;
        y->marked = false;
    }
    int extractMax(){
        Node* z = this->maxNode;
        if(z != nullptr){
            if(z->child != nullptr) {
                this->extractChildrenToRootList(z->child);
            }
            this->removeMax();
            if(z == z->right){
                if(this->head == z) this->head = nullptr;
                this->maxNode = nullptr;
            }
            else {
                if(this->head == maxNode) this->head = z->right;
                this->maxNode = z->right;
                this->consolidate(this->head);
            }
            this->size--;
        }
        return z->value;
    }

    void removeMax(){
        Node* left = this->maxNode->left;
        Node* right = this->maxNode->right;
        left->right = right;
        right->left = left;
    }

    FibonacciHeap& operator=(const FibonacciHeap& fh){
        if(this!=&fh){
            if(fh.head != nullptr){
                this->head = fh.head;
            }
            if(fh.maxNode != nullptr){
                this->maxNode = fh.maxNode;
            }
            this->size = fh.size;
        }
        return *this;
    };
};

int main()
{

    ifstream f("C:\\Users\\tiril\\CLionProjects\\FibonacciHeap\\mergeheap.in");
    ofstream g("C:\\Users\\tiril\\CLionProjects\\FibonacciHeap\\mergeheap.out");
    int N, Q, a, b, c;
    vector<FibonacciHeap*> heaps;
    f>>N; f>>Q;
    for(int i=0; i<=N; i++){
        heaps.push_back(new FibonacciHeap);
    }

    while(Q>0){
        f>>a;
        if(a == 2) f>>b;
        else f>>b>>c;
        switch(a){
            case 1: {
                heaps[b]->insert(c);
                break;
            }
            case 2: {
                g<<heaps[b]->extractMax()<<endl;
                break;
            }
            case 3: {
                *heaps[b] = heaps[b]->heapUnion(*heaps[c]);
                heaps[c] = new FibonacciHeap();
                break;
            }
            default: {
                break;
            }
        }
        Q--;
    }
    f.close();
    g.close();

    return 0;
}