#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;
    int 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;
    int 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 = 0;
public:
    FibonacciHeap(){ this->maxNode = nullptr; this->head = nullptr; }
    FibonacciHeap(int size, Node* max, Node* H){
        this->size = size;
        this->maxNode = max;
        this->head = H;
    }
    void insert(int val){
        Node* n = new Node;
        n->value = val;
        n->left = n;
        n->right = n;
        n->parent = nullptr;
        n->child = nullptr;
        n->degree = 0;
        if(this->maxNode == NULL){
            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;
    }

    void getMax(){
        if(this->maxNode != nullptr){
            cout<<"max: "<<this->maxNode->value<<":::::::";
        } else {
            cout<<"max doesn't exist!"<<endl;
        }
    }

    Node* find(int val){
        return this->findNode(val, this->head);
    }
    Node* findNode(int val, Node* n){
        if(n->value == val) return n;
        if(n->right != nullptr){
            if(n->right->seen == false){
                n->right->seen = true;
                Node* foundNode = findNode(val, n->right);
                n->right->seen = false;
                if(foundNode != nullptr) return foundNode;
            }
        }
        if(n->child != nullptr){
            if(n->child->seen == false){
                n->child->seen = true;
                Node* foundNode2 = findNode(val, n->child);
                n->child->seen = false;
                if(foundNode2 != nullptr) return foundNode2;
            }
        }
    }

    FibonacciHeap& heapUnion(FibonacciHeap& heap2) {
//        cout<<*this->head<<endl<<*heap2.head<<endl;
//        this->showHeap(); cout<<endl;
//        heap2.showHeap(); cout<<endl;

        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;
        Node* loop = child;
        while(loop->parent != nullptr){
            loop->parent = nullptr;
            loop = loop->right;
        }
    }
    void consolidate(Node* H){
        vector<Node*> A = {}, uncheck = {};
        for(int i=0; i<this->size; i++){
            A.push_back(nullptr);
        }
        int d;
        Node* w = this->head;
        while(w->seen == false){
            w->seen = true;
            uncheck.push_back(w);
            Node* x = w;
            int d = x->degree;
            bool i = 0;
            while(A[d] != nullptr){
                Node* y = A[d];
                if(x->value < y->value) {
                    Node *aux = x;
                    x = y;
                    y = aux;
                }
                this->link(this->head, y, x);
                A[d] = nullptr;
                d = d + 1;
            }
            A[d] = x;
            w = x->right;
        }

        for(int i=0; i<uncheck.size(); i++){
            uncheck[i]->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){
        // remove y from root list
        Node* left = y->left;
        Node* right = y->right;
        left->right = right;
        right->left = left;

            // make y child of x
            if(x->child != nullptr){
                Node* child = x->child;
                Node* last = child->left;
                y->right = child;
                y->left = last;
                last->right = y;
                child->left = y;
                y->parent = x;
            } else {
                x->child = y;
                y->parent = x;
                y->left = y;
                y->right = y;
            }
        x->degree++;
        y->marked = false;
    }
    Node* 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;
    }

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

    void showHeap(Node* parent = NULL, Node* node = NULL){
        if(this->head == nullptr){
            cout<<"HEAP EMPTY!"<<endl;
            return;
        }
        if(node == NULL) node = this->head;
        node->seen = true;
        if(parent != NULL) cout<<"p: "<<parent->value<<" c: "<<node->value<<" ";
        else cout<<"node: "<<node->value<<" ";

        if(node->right != NULL) {
            if (!node->right->seen) {
                this->showHeap(parent, node->right);
            }
        }
        if(node->child != NULL) {
            if (!node->child->seen) {
                this->showHeap(node, node->child);
            }
        }
        node->seen = false;
    }
    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\\Patric\\CLionProjects\\FibonacciHeapImplementation\\mergeheap.in");
    ofstream g("C:\\Users\\Patric\\CLionProjects\\FibonacciHeapImplementation\\mergeheap.out");
    int N, Q, a, b, c;
    vector<FibonacciHeap*> heaps;
    f>>N; f>>Q;
    for(int i=0; i<=N; i++){
        FibonacciHeap heap;
        heaps.push_back(new FibonacciHeap);
    }

//    ifstream f4("C:\\Users\\Patric\\CLionProjects\\FibonacciHeapImplementation\\correctoutput.out");
//    int d;
    while(Q>0){
        f>>a;
        cout<<endl<<Q<<endl;
        if(a == 2) f>>b;
        else f>>b>>c;
        switch(a){
            case 1: {
//                cout<<endl;
//                heaps[b]->getMax(); cout<<b<<endl;
//                cout<<"INSERT IN "<<b<<" VALUE "<<c<<": "<<endl;
                heaps[b]->insert(c);
//                heaps[b]->getMax(); cout<<b<<endl;
//                cout<<endl;
                break;
            }
            case 2: {
//                cout<<endl;
//                heaps[b]->getMax(); cout<<b<<endl;
                Node* Max = heaps[b]->extractMax();
//                f4>>d;
//                cout<<"EXTRACT MAX FROM "<<b<<": "<<Max->value<<endl;
//                if(d != Max->value) cout<<"WRONG!: "<<d<<" "<<Max->value<<endl;
                g<<Max->value<<endl;
//                heaps[b]->getMax(); cout<<b<<endl;
//                cout<<endl;
                break;
            }
            case 3: {
//                cout<<endl;
//                heaps[b]->getMax(); cout<<b<<endl;
//                cout<<"UNIFY HEAPS "<<b<<" AND "<<c<<endl;
                *heaps[b] = heaps[b]->heapUnion(*heaps[c]);
                heaps[c] = new FibonacciHeap();
//                heaps[b]->getMax(); cout<<b<<endl;
//                cout<<endl;
                break;
            }
            default: {
//                cout<<"BAD INPUT!"<<endl;
                break;
            }
        }
        Q--;
    }
    f.close();
    g.close();
//
//
//    cout<<"=============================================================================================="<<endl;
//    int m, k = 0, n, e;
//    vector<int> v1 = {}, v2 = {};
//    ifstream f2("C:\\Users\\Patric\\CLionProjects\\FibonacciHeapImplementation\\mergeheap.out");
//    ifstream f3("C:\\Users\\Patric\\CLionProjects\\FibonacciHeapImplementation\\correctoutput.out");
//
//    while(f2>>m){
//        v1.push_back(m);
//    }
//    while(f3>>m){
//        v2.push_back(m);
//    }
//    for(int i=0; i<v1.size(); i++){
//        for(int j=0; j<v2.size(); j++){
//            if(v1[i] == v2[j]){
//                v1.erase(v1.begin() + i);
//                v2.erase(v2.begin() + j);
//                i--;
//                j--;
//            }
//        }
//    }
//    cout<<endl<<"SIZES: "<<endl;
//    cout<<v1.size()<<" "<<v2.size()<<endl;
//    for(int i=0; i<v1.size(); i++){
//        cout<<v1[i]<<" ";
//    }
//    cout<<endl;
//
//    for(int i=0; i<v2.size(); i++){
//        cout<<v2[i]<<" ";
//    }
//    cout<<endl;

//    FibonacciHeap heap;
//    heap.insert(23);
//    heap.insert(52);
//    heap.insert(746);
//    heap.insert(824);
//    heap.insert(264);
//    heap.insert(2398);
//    heap.insert(120);
//    heap.insert(84563);
//    heap.insert(6321);
//    heap.insert(37235);
//    heap.insert(1235);
//    heap.insert(37);
//    heap.insert(7644);
//    heap.insert(8087);
//    heap.insert(12);
//    heap.insert(23756);
//    heap.insert(634);
//    heap.showHeap();
//    cout<<endl<<endl;
//    cout<<*heap.extractMax();
//    heap.showHeap();
//    cout<<endl;
//    heap.insert(259);
//    heap.insert(25863);
//    heap.insert(2376);
//    heap.showHeap();
//    cout<<"++++++++++++++++++++++++++++++++"<<endl;
//    cout<<*heap.extractMax()<<endl;
//    heap.showHeap();
    return 0;
}