#include <iostream>
#include <vector>
#include <ostream>
#include <istream>
#include <fstream>

using namespace std;
int show = 0;

class Node{
    int value, nrChildren;
    Node* left;
    Node* right;
    Node* parent;
    Node* child;
    bool seen; // pentru find
    bool lostChild; // pentru functia de increaseKey, se muta si parintii recursiv in lista de roots daca marked = true
public:
    Node();
    Node(int);
    Node(const Node& node);

    friend ostream& operator<<(ostream& out, const Node& node);

    int getValue() const { return this->value; }
    Node* getLeft() const { return this->left; }
    Node* getRight() const { return this->right; }
    Node* getParent() const { return this->parent; }
    Node* getChild() const { return this->child; }
    bool seenNode() const { return this->seen; }
    bool getLostChild() const { return this->lostChild; }
    int getNrChildren() const { return this->nrChildren; }

    void setLeft(Node* n) { this->left = n; }
    void setRight(Node* n) { this->right = n; }
    void setParent(Node* n) { this->parent = n; }
    void setChild(Node* n) { this->child = n; }
    void setSeen(bool set) { this->seen = set; }
    void setValue(int val) { this->value = val; }
    void setLostChild(bool set) { this->lostChild = set; }
    void decreaseNrChildren() { this->nrChildren--; }
    void increaseNrChildren() { this->nrChildren++; }
};
Node::Node(){
    this->value = 0;
    this->nrChildren = 0;
    this->left = NULL;
    this->right = NULL;
    this->parent = NULL;
    this->child = NULL;
    this->seen = false;
    this->lostChild = false;
}
Node::Node(int value){
    this->value = value;
    this->nrChildren = 0;
    this->left = NULL;
    this->right = NULL;
    this->parent = NULL;
    this->child = NULL;
    this->seen = false;
    this->lostChild = false;
}
Node::Node(const Node& node){
    this->value = node.value;
    this->nrChildren = node.nrChildren;
    this->left = node.left;
    this->right = node.right;
    this->parent = node.parent;
    this->child = node.child;
    this->seen = node.seen;
    this->lostChild = node.lostChild;
}
ostream& operator <<(ostream& out, const Node& node){
    out<<"Value: "<<node.value<<endl;
    if(node.getLeft() != NULL) out<<"Left: "<<node.left->value<<endl;
    if(node.getRight() != NULL) out<<"Right: "<<node.right->value<<endl;
    if(node.getParent() != NULL) out<<"Parent: "<<node.parent->value<<endl;
    if(node.getChild() != NULL) out<<"Child: "<<node.child->value<<endl;
    out<<"Nr of children: "<<node.getNrChildren()<<endl;
    out<<"Seen: "<<node.seen<<endl;
    out<<"Lost child: "<<node.lostChild<<endl;

    return out;
}

class FibonacciHeap{
    int nrOfNodes;
    Node* max;
    Node* H;
    int maxDegree;
public:
    FibonacciHeap();
    FibonacciHeap(int, Node*, Node*, int);
    FibonacciHeap(const FibonacciHeap& heap);
    int getMax(){
        return this->max->getValue();
    }
    Node* insert(int);
    void addToRootList(Node&);
    void changeMax(Node& n) {
        if(this->max == NULL) this->max = &n;
        else {
            if(n.getValue() > this->max->getValue()) this->max = &n;
        }
    };
    FibonacciHeap heapUnion(FibonacciHeap&);
    Node* find(int, Node*);
    void increaseKey(int, int);
    void cutOut(Node*);
    Node* extractToRootList(Node*, Node*);
    Node* extractMax();
    void merge();
    Node* mergeTwoHeaps(Node*, Node*);
    void func(vector<vector<Node*>>&, int, Node*);
    void showHeap(Node*, Node*);
    void clearSeen(Node*);
    void findNewMax(Node*);
    Node* findNode(int);

    FibonacciHeap& operator =(const FibonacciHeap& heap);
};
FibonacciHeap::FibonacciHeap(){
    this->H = NULL;
    this->max = NULL;
    this->nrOfNodes = 0;
    this->maxDegree = 0;
}
FibonacciHeap::FibonacciHeap(int nrOfNodes, Node* max, Node* H, int maxDegree){
    this->nrOfNodes = nrOfNodes;
    this->max = max;
    this->H = H;
    this->maxDegree = maxDegree;
}
FibonacciHeap::FibonacciHeap(const FibonacciHeap& heap){
    this->nrOfNodes = heap.nrOfNodes;
    this->H = heap.H;
    this->max = heap.max;
    this->maxDegree = heap.maxDegree;
}
Node* FibonacciHeap::insert(int val){
    Node* n = new Node;
    n->setValue(val);
    n->setLeft(n);
    n->setRight(n);
    n->setParent(NULL);
    n->setChild(NULL);
    this->addToRootList(*n);
    this->changeMax(*n);
    this->nrOfNodes++;
    return this->H;
}
void FibonacciHeap::addToRootList(Node& n){
    if(this->H == NULL) {
        this->H = &n;
    }
    else {
        n.setRight(this->H);
        n.setLeft(this->H->getLeft());
        this->H->getLeft()->setRight(&n);
        this->H->setLeft(&n);
    }
}
FibonacciHeap FibonacciHeap::heapUnion(FibonacciHeap& heap2) {
    FibonacciHeap heap1(this->nrOfNodes, this->max, this->H, this->maxDegree);
    if(heap2.max->getValue() > this->max->getValue()){
        heap1.max = heap2.max;
    }
    heap1.nrOfNodes += heap2.nrOfNodes;

    Node* heap2End = heap2.H->getLeft();
    heap2.H->setLeft(heap1.H->getLeft());
    heap1.H->getLeft()->setRight(heap2.H);
    heap1.H->setLeft(heap2End);
    heap1.H->getLeft()->setRight(heap1.H);

    return heap1;
}
Node* FibonacciHeap::find(int val, Node* node){
    node->setSeen(true);
    Node* res = NULL;
    if(node->getValue() == val){
        node->setSeen(false);
        res = node;
        return res;
    }
    if(res == NULL){
        if(node->getChild() != NULL && node->getChild()->seenNode() == false){
            res = FibonacciHeap::find(val, node->getChild());
            if(res!=NULL) cout<<res->getValue()<<endl;
        }
        if(node->getRight() != NULL && node->getRight()->seenNode() == false && (res == NULL || res->getValue() != val)){
            if(res!=NULL) cout<<res->getValue()<<endl;
            res = FibonacciHeap::find(val, node->getRight());
        }
    }
    node->setSeen(false);
    return res;
}
Node* FibonacciHeap::extractToRootList(Node* n, Node* parent){
    if(parent != NULL){
        if(n->getRight() != n) {
            parent->setChild(n->getRight());
        } else {
            parent->setChild(NULL);
        }
        parent->decreaseNrChildren();
    }

    Node* left = n->getLeft();
    Node* right = n->getRight();
    if(left != NULL && right != NULL){
        n->getLeft()->setRight(n->getRight());
        n->getRight()->setLeft(n->getLeft());
    }
    n->setLeft(n);
    n->setRight(n);

    Node* last = this->H->getLeft();

    if(last != NULL){
        last->setRight(n);
    }
    n->setRight(this->H);
    n->setLeft(last);
    this->H->setLeft(n);

    n->setParent(NULL);

    return parent->getChild();
}
void FibonacciHeap::cutOut(Node* n){
    Node* parent = n->getParent();

    extractToRootList(n, parent);

    if(parent != NULL){
        if(!parent->getLostChild())
            parent->setLostChild(true);
        else this->cutOut(parent);
    }
}
void FibonacciHeap::increaseKey(int val, int newVal){
    Node* n = this->find(val, this->H);
    if(n == NULL){
        cout<<"Key not found!"<<endl;
    } else {
        n->setValue(newVal);
        if(n->getParent() != NULL){
            if(newVal <= n->getParent()->getValue()){
                cout<<"Done!"<<endl;
                return;
            } else {
                this->cutOut(n);
                cout<<"Done!"<<endl;
            }
        }
        if(newVal > this->max->getValue()) this->max = n;
    }
}
void FibonacciHeap::showHeap(Node* parent = NULL, Node* node = NULL){
    if(node == NULL) node = this->H;
    node->setSeen(true);
    if(parent != NULL) cout<<"p: "<<parent->getValue()<<" c: "<<node->getValue()<<" ";
    else cout<<"node: "<<node->getValue()<<" ";

//    cout<<"NODE: "<<*node<<endl;

    if(node->getRight() != NULL) {
        if (!node->getRight()->seenNode()) {
            this->showHeap(parent, node->getRight());
        }
    }
    if(node->getChild() != NULL) {
        if (!node->getChild()->seenNode()) {
            this->showHeap(node, node->getChild());
        }
    }
    node->setSeen(false);
}
Node* FibonacciHeap::mergeTwoHeaps(Node* head1, Node* head2){
    this->H = head1;
    if(head1->getLeft() == head2){
        head1->setLeft(head2->getLeft());
        head1->getLeft()->setRight(head1);
    }
    if(head1->getRight() == head2){
        head1->setRight(head2->getRight());
        head1->getRight()->setLeft(head1);
    }

    if(head1->getNrChildren() == 0) {
        head1->setChild(head2);
        head2->getLeft()->setRight(head2->getRight());
        head2->getRight()->setLeft(head2->getLeft());
        head2->setLeft(head2);
        head2->setRight(head2);
    } else {
        Node* child = head1->getChild();
        Node* last = child->getLeft();

        head2->getLeft()->setRight(head2->getRight());
        head2->getRight()->setLeft(head2->getLeft());

        last->setRight(head2);
        head2->setRight(child);
        head2->setLeft(last);
        child->setLeft(head2);
    }


    head2->setParent(head1);

    head1->increaseNrChildren();
    return head1;
}
void FibonacciHeap::func(vector<vector<Node*>>& heaps, int nrChildren, Node* head){
//    if(show) cout<<"HA21"<<endl;
    if(nrChildren == this->maxDegree){
        this->maxDegree+=1;
        heaps.push_back({});
    }
//    if(show) cout<<heaps.size()<<" "<<nrChildren+1<<endl;
//    while(heaps.size() < nrChildren+1)
//        heaps.push_back({});
//    if(show) cout<<heaps.size()<<" "<<nrChildren+1<<endl;

    if(heaps[nrChildren+1].size() == 0){
        if(heaps[nrChildren][0]->getValue() > head->getValue()){
            Node* newHeapHead(this->mergeTwoHeaps(heaps[nrChildren][0], head));
            heaps[nrChildren+1].push_back(newHeapHead);
        } else {
            Node* newHeapHead(this->mergeTwoHeaps(head, heaps[nrChildren][0]));
            heaps[nrChildren+1].push_back(newHeapHead);
        }
    } else {
        if(heaps[nrChildren][0]->getValue() > head->getValue()){
            Node* newHeapHead(this->mergeTwoHeaps(heaps[nrChildren][0], head));
            this->func(heaps, nrChildren+1, newHeapHead);
        } else {
            Node* newHeapHead(this->mergeTwoHeaps(head, heaps[nrChildren][0]));
            this->func(heaps, nrChildren+1, newHeapHead);
        }
    }
    heaps[nrChildren].clear();
}
void FibonacciHeap::merge(){
    vector<vector<Node*>> heaps(this->maxDegree+1);
    vector<Node*> toUnseen = {};
    Node* head = this->H;
    cout<<"=========================================================================="<<endl;
    cout<<heaps.size()<<endl;
    while(!head->seenNode()) {
        cout<<"HEAD: "<<endl<<*head<<endl;
        head->setSeen(true);
        toUnseen.push_back(head);
        int nrChildren = head->getNrChildren();
        Node *right = head->getRight();

        if(heaps.size() > nrChildren) {
            if (heaps[nrChildren].size() == 0) {
                heaps[nrChildren] = {};
                heaps[nrChildren].push_back(head);
            } else {
                this->func(heaps, nrChildren, head);
            }
        } else {
            while(heaps.size() <= nrChildren){
                heaps.push_back({});
                this->maxDegree+=1;
            }
        }

        head = right;
    }


    for(long unsigned int i=0; i<toUnseen.size(); i++){
        toUnseen[i]->setSeen(false);
    }
}
Node* FibonacciHeap::extractMax(){
    Node* child = this->max->getChild();
    Node* max = this->max;
    while(child != NULL){
        child = extractToRootList(child, this->max);
    }

    if(this->H == this->max){
        if(this->max->getRight() == this->max) this->H = NULL;
        this->H = this->max->getRight();  // SA VAD CUM ASEZ HEAD IN ASA FEL INCAT SA NU STRICE NIMIC
    }
    if(this->max->getLeft() != NULL)
        this->max->getLeft()->setRight(this->max->getRight());
    if(this->max->getRight() != NULL)
        this->max->getRight()->setLeft(this->max->getLeft());
    this->merge();

    if(this->max->getRight() != this->max){
        this->max = this->max->getRight();
        this->findNewMax(this->H);
    } else this->max = NULL;
    return max;
}
void FibonacciHeap::findNewMax(Node* node){
    if(node->seenNode()) {
        node->setSeen(false);
        return;
    }

    node->setSeen(true);
    if(this->max->getValue() < node->getValue())
        this->max = node;
    findNewMax(node->getRight());
    node->setSeen(false);
}
Node* FibonacciHeap::findNode(int val){
    return this->find(val, this->H);
}
FibonacciHeap& FibonacciHeap::operator=(const FibonacciHeap& heap){
    if(this != &heap){
        this->nrOfNodes = heap.nrOfNodes;
        this->max = heap.max;
        this->H = heap.H;
        this->maxDegree = heap.maxDegree;
    }
    return *this;
}
int main() {
    ifstream f("C:\\Users\\Patric\\CLionProjects\\FibonacciHeap\\mergeheap.in");
    ofstream g("C:\\Users\\Patric\\CLionProjects\\FibonacciHeap\\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(heap);
    }
    while(Q>0){
        if(Q==63) show = 1;
        f>>a;
        if(a == 2) f>>b;
        else f>>b>>c;
        switch(a){
            case 1: {
                if(Q==63) cout<<"HA1"<<endl;
                heaps[b].insert(c);
                break;
            }
            case 2: {
                if(show) cout<<"HA2"<<endl;
                Node* Max = heaps[b].extractMax();
                if(show) cout<<"HA5"<<endl;
                g<<Max->getValue()<<endl;
                break;
            }
            case 3: {
                if(show) cout<<"HA3"<<endl;
                heaps[b] = heaps[b].heapUnion(heaps[c]);
                break;
            }
            default: {
                cout<<"BAD INPUT!"<<endl;
                break;
            }
        }
        Q--;
    }
    f.close();
    g.close();

    return 0;
}