#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <windows.h>
#include <chrono>
#include <thread>
#include <fstream>

using namespace std;

void pause(int seconds)
{
    this_thread::sleep_for(chrono::seconds(seconds));
}

void clearScreen()
{
    system("CLS");
}

void Menu1()
{
    clearScreen();
    cout << "\n1-Test the Fibonacci Heap A";
    cout << "\n2-Create your own Fibonacci Heap";
    cout << "\n3-Stop";
    cout << endl;

}

void Menu2()
{
    clearScreen();
    cout << "\n1-Test the Fibonacci Heap A";
    cout << "\n2-Back to your own Fibonacci Heap";
    cout << "\n3-Stop";
    cout << endl;

}

void Menu3()
{
    clearScreen();
    cout << "\n1-Insertion";
    cout << "\n2-Find Minimum";
    cout << "\n3-Merge";
    cout << "\n4-Decrease Key";
    cout << "\n5-Delete";
    cout << "\n6-Extract Minimum";
    cout << "\n7-Display Fibonacci Heap 1 (The Root List)";
    cout << "\n8-Display Fibonacci Heap 2 (All The Nodes)";
    cout << "\n9-Display Nodes' Information";
    cout << "\n10-Back";

    cout << endl;

}

struct Node
{

    int key; /// The value of the node
    int degree; /// The number of children of the node
    bool marked; /// Whether the node is marked
    Node* parent; /// The parent of the node
    Node* left; /// The left sibling of the node
    Node* right; /// The right sibling of the node
    Node* child; /// One of the node's children (if any)
    bool seen; /// For extract-min, to know when to exit the while(true)

    Node(int key);

};

Node::Node(int key)
{
    this->key = key;
    this->degree = 0;
    this->parent = nullptr;
    this->child = nullptr;
    this->left = this;
    this->right = this;
    this->marked = false;
    this->seen=false;
}

ostream& operator<<(ostream& out, const Node& obj) /// For testing purposes / for the interactive menu (to see all attributes of a node)
{
    out<<"The key (value) of the node : ";
    out<<obj.key<<endl;
    out<<"The degree of the node : ";
    out<<obj.degree<<endl;
    if(obj.parent==nullptr)
        out<<"The node is a root (has no parent)"<<endl;
    else
    {
        out<<"The parent of the node is : ";
        out<<obj.parent->key<<endl;
    }
    if(obj.child==nullptr)
        out<<"The node has no children"<<endl;
    else
    {
        out<<"The \"favorite\" child : ";
        out<<obj.child->key<<endl;
        if(obj.degree>1)
        {
            out<<"The children of the node : ";
            Node* current=obj.child;
            do
            {
                if(current->right==obj.child)
                    out << current->key;
                else
                    out << current->key << " --> ";
                current = current->right;
            }
            while (current != obj.child);
            out<<endl;
        }

    }

    out<<"The left sibling of the node : ";
    out<<obj.left->key<<endl;
    out<<"The right sibling of the node : ";
    out<<obj.right->key<<endl;
    if (obj.marked==true)
        out<<"The node is marked"<<endl;
    else
        out<<"The node is not marked"<<endl;
    if (obj.seen==true)
        out<<"The node is seen"<<endl;
    else
        out<<"The node is not seen"<<endl;

    out<<endl;
    return out;
}

class FibonacciHeap
{
private:

    /// Number of nodes in the heap
    int n;
    /// Pointer to the minimum node in the heap
    Node* minNode;
    /// Vector with all the nodes from the Fibonacci Heap (This was added for testing / for the interactive menu)
    vector<Node*> nodes;

public:

    FibonacciHeap();

    /// Methods for testing / for the interactive menu
    int getN();
    Node* getMinNode();
    vector<Node*> getNodes();
    void setNodes(vector<Node*> newNodes);
    void setMinNode(Node* x);
    void setN(int n);
    void displayFibonacciHeap();
    void displayAllNodes();
    void deleteNodes(Node* start);

    /// Important Methods (The operations of the Fibonacci Heap)
    int findMin();
    Node* insert(int key); /// This was adjusted to be "Node*" instead of "void" for testing purposes / for the interactive menu
    void merge(FibonacciHeap& FH);
    void decreaseKey(Node* x, int key);
    Node* extractMax(); /// This was adjusted to be "Node*" instead of "int" for testing purposes / for the interactive menu
    Node* deleteNode(Node* x); /// This was adjusted to be "Node*" instead of "void" for testing purposes / for the interactive menu


    ~FibonacciHeap();



};

FibonacciHeap::FibonacciHeap()
{
    this->minNode = nullptr;
    this->n = 0;
    this->nodes=vector<Node*> ();
}

int FibonacciHeap::findMin()
{
    if (this->minNode == nullptr)
    {
        cout << "The Fibonacci Heap is empty." << endl;
        return 0;
    }

    return this->minNode->key;
}

Node* FibonacciHeap::insert(int key)
{
    /// Create a new node with the given key
    Node* node = new Node(key);

    /// Add the new node to the root list
    if (this->minNode == nullptr)
    {
        this->minNode = node;
        this->minNode->left = this->minNode;
        this->minNode->right = this->minNode;
    }
    else
    {
        this->minNode->left->right = node;
        node->left = this->minNode->left;
        this->minNode->left = node;
        node->right = this->minNode;

        /// Update minimum node if necessary
        if (node->key > this->minNode->key)
        {
            this->minNode = node;
        }
    }

    this->n++;
    return node;

}

void FibonacciHeap::merge(FibonacciHeap& FH)
{
    int i=0;

    /// If this Fibonacci heap is empty, set its minimum node to be the minimum node of FH
    if (this->minNode == nullptr)
    {
        this->minNode=FH.minNode;
        i++;
    }

    /// If FH is empty, do nothing
    if (FH.minNode == nullptr)
    {
        i++;
    }

    /// If both heaps are not empty, merge their root lists
    if(i==0)
    {
        /// Get the minimum nodes and their right nodes from both heaps
        Node* minNode1 = this->minNode;
        Node* minNode2 = FH.minNode;
        Node* minNode1Right = minNode1->right;
        Node* minNode2Right = minNode2->right;

        /// Link the two root lists together
        minNode1->right = minNode2Right;
        minNode2Right->left = minNode1;
        minNode2->right = minNode1Right;
        minNode1Right->left = minNode2;

        /// Update the minimum node if necessary
        if (FH.minNode->key>this->minNode->key)
            this->minNode=FH.minNode;
    }

    /// Update the size of this Fibonacci heap by adding the size of FH
    this->n += FH.n;

    /// Clear FH
    FH.minNode = nullptr;
    FH.n = 0;
}

void FibonacciHeap::decreaseKey(Node* x, int key)
{
    if (key > x->key)
    {
        /// New key is greater than current key, error
        return;
    }

    x->key = key;
    Node* y = x->parent;

    if(y==nullptr) /// The case if x is already in the root list
    {
        if (x->key < this->minNode->key)
        {
            this->minNode = x;
        }

        return;
    }

    if(y->key<=x->key) /// The case if the decrease key does not violate the min heap property
        return;

    if(x->right==x && x->left==x) /// If x is the only child of it's parent y, update the child pointer of y to nullptr
        y->child=nullptr;

    if (y->child==x) /// If y has more children (not just x)
    {
        y->child=x->right; /// If the pointer of child of y is to x (that we need to cut and add to the root list), update it to point to the next child (right sibling of x)
        x->left->right=x->right; /// Link the left and right of x (because we will cut x)
        x->right->left=x->left;
    }
    else
    {
        x->left->right=x->right; /// Link the left and right of x (because we will cut x)
        x->right->left=x->left;
    }

    /// Cut x from his parent and move it to the root list
    this->minNode->left->right = x;
    x->left = this->minNode->left;
    this->minNode->left = x;
    x->right = this->minNode;
    x->parent=nullptr;
    x->marked=false;

    /// Update minimum node if necessary
    if (x->key < this->minNode->key)
    {
        this->minNode = x;
    }

    y->degree--;

    if (y->marked==false) /// If parent of x is not marked, mark it
    {
        y->marked=true;
        if(y->parent==nullptr) /// If parent of x is a root, don't mark it because it is redundant
            y->marked=false;
        return;
    }

    else

        while (y->marked==true && y->parent!=nullptr)
        {
            /// We make x the new z, y the parent of y, and do the same thing as before
            Node* z=y;
            y=y->parent;

            if(z->right==z && z->left==z) /// If z is the only child of it's parent y, update the child pointer of y to nullptr
                y->child=nullptr;

            if (y->child==z)
            {
                y->child=z->right; /// If the pointer of child of y is to z (that we need to cut and add to the root list), update it to point to the next child (right sibling of z)
                z->left->right=z->right; /// Link the left and right of z (because we will cut z)
                z->right->left=z->left;
            }
            else
            {
                z->left->right=z->right; /// Link the left and right of z (because we will cut z)
                z->right->left=z->left;

            }

            /// Cut z from his parent and move it to the root list
            this->minNode->left->right = z;
            z->left = this->minNode->left;
            this->minNode->left = z;
            z->right = this->minNode;
            z->parent=nullptr;
            z->marked=false;

            /// Update minimum node if necessary
            if (z->key < this->minNode->key)
            {
                this->minNode = z;
            }

            y->degree--;
        }

    y->marked=true; /// If y is not a root, mark it

    if(y->parent==nullptr) /// If y is a root, don't mark it because it is redundant
        y->marked=false;
}

Node* FibonacciHeap::extractMax()
{
    if (this->minNode == nullptr)
    {
        cout << "The Fibonacci Heap is empty." << endl;
        return this->minNode;
    }
    this->minNode->degree=0;
    Node* oldMinNode=this->minNode; /// Keep the current minNode, because we will return it later
    int maxDegree = ceil(log2(this->n))+1;/// The maximum possible degree from the Fibonacci Heap
    vector<Node*> degreeNodes(maxDegree, nullptr); /// The vector with the length of maxDegree for later

    if (this->minNode->child!=nullptr) /// If this->minNode has children
    {
        Node* current = this->minNode->child; /// Make every child's parent pointer to nullptr
        do
        {
            current->parent=nullptr;
            current = current->right;
        }
        while (current != this->minNode->child);

        this->minNode->right->left = current->left; /// Add all children of this->minNode to the root list
        current->left->right = this->minNode->right;
        this->minNode->right = current;
        current->left = this->minNode;

        this->minNode->child=nullptr; /// We don't need this anymore since we are going to cut this->minNode
    }

    Node* newMinNode=this->minNode->right; /// Set a temporary minNode to be able to continue

    if(this->minNode == newMinNode) /// If this->minNode is the only node in the root list, stop here
    {
        this->minNode=nullptr;
        this->n--;
        return oldMinNode;
    }

    this->minNode->left->right=this->minNode->right; /// Link the left and right of this->minNode (because we will cut this->minNode)
    this->minNode->right->left=this->minNode->left;

    this->minNode->left=nullptr; /// Make the left and right of the this->minNode nullptr because we have already linked its siblings and will soon need to remove it
    this->minNode->right=nullptr;

    this->minNode=newMinNode; /// Update this->minNode


    Node* current=this->minNode; /// We are getting to the combining of the trees with the same degree part. We start from this->minNode

    while (true)
    {
        if(current->seen==true) /// So if we encounter a previously visited node, it means we have completed our job here
            break;
        Node* next = current->right; /// To be able to keep in mind where we need to go next
        int degree = current->degree; /// Get current node degree

        while(degreeNodes[degree] != nullptr) /// While (degreeNodes[degree] != nullptr), we ensure that the current node is combined with every other node of the same degree
        {
            Node* other = degreeNodes[degree]; /// Take the element from the vector
            degreeNodes[degree] = nullptr; /// Reset the degreeNodes[degree]

            if (current->key < other->key) /// To make every time "other" a child of "current"
            {
                swap(current, other);
            }
            other->seen = false; /// This will be important for next extractMin operations

            /// Link "other" as a child of "current"

            other->left->right=other->right; /// Link the left and right of "other" (because we will cut "other")
            other->right->left=other->left;

            other->parent=current; /// Update its parent to "current"

            degree++; /// Update degree of "current", "other" is now a child of "current" so +1
            current->degree++;

            if (current->child == nullptr) /// If "current" has no previous children just set its child pointer to "other"
            {
                current->child = other;
                other->right = other->left = other; /// Set the left and right of "other" to himself
            }
            else
            {
                /// If "current" has children, merge "other" to "current's" children
                current->child->left->right = other;
                other->left = current->child->left;
                other->right = current->child;
                current->child->left = other;
            }
        }
        current->seen=true; /// To know that we have visited the current node

        degreeNodes[degree] = current; /// Update degreeNodes[degree]

        if (current->key > this->minNode->key) /// Update the minimum if necesarry
        {
            this->minNode = current;
        }

        current = next; /// Go to the next node that we need to visit
    }

    Node* current2 = this->minNode; /// Set the "seen" attribute to false for every root to prepare for the next extractMin operation
    do
    {
        current2->seen=false;
        current2 = current2->right;
    }
    while (current2 != this->minNode);

    this->n--;

    return oldMinNode;
}

Node* FibonacciHeap::deleteNode(Node* x)
{
    /// Decrease the key of the node to be deleted to the maximum negative integer
    decreaseKey(x,(-(1<<31)));
    /// Extract the minimum node (which will be the node with the decreased key)
    Node* y=extractMax();
    return y;
}


int FibonacciHeap::getN()
{
    return this->n;
}
Node* FibonacciHeap::getMinNode()
{
    return this->minNode;
}
vector<Node*> FibonacciHeap::getNodes()
{
    return this->nodes;
}
void FibonacciHeap::setNodes(vector<Node*> newNodes)
{
    this->nodes = newNodes;
}
void FibonacciHeap::setMinNode(Node* x)
{
    this->minNode=x;
}
void FibonacciHeap::setN(int n)
{
    this->n=n;
}

void FibonacciHeap::displayFibonacciHeap()
{
    if (this->minNode == nullptr)
    {
        cout << "The Fibonacci Heap is empty." << endl;
        return;
    }
    cout<<"The root nodes of the Fibonacci Heap are : ";
    Node* current = this->minNode;

    do
    {
        if(current->right==this->minNode)
            cout << current->key;
        else
            cout << current->key << " --> ";
        current = current->right;
    }
    while (current != this->minNode);
    cout<<endl;
    cout<<"The Fibonacci Heap has " << this->n << " nodes.";
    cout<<endl;
}

void FibonacciHeap::displayAllNodes()
{
    if(this->minNode==nullptr || this->nodes.size()==0)
    {
        cout<<"The Fibonacci Heap is empty."<<endl<<endl;
        return;
    }
    for(int i=0; i<this->nodes.size(); i++)
        cout<<i<<". "<<this->nodes[i]->key<<endl;
    cout<<endl;
}

void FibonacciHeap::deleteNodes(Node* start)
{
    if (start != nullptr)
    {
        Node* current = start;
        do
        {
            Node* temp = current;
            current = current->right;
            deleteNodes(temp->child);
            delete temp;
        }
        while (current != start);
    }
}

FibonacciHeap::~FibonacciHeap()
{
    if (minNode != nullptr)
    {
        deleteNodes(minNode);
    }
}

int main()
{
    ifstream f1("mergeheap.in");
    ofstream f2("mergeheap.out");
int N;
int Q;
f1>>N;
f1>>Q;
vector<FibonacciHeap> lista (N);

while(Q!=0)
{   int y;
    f1>>y;
    if(y==1)
    {   int nr;
        int x;
        f1>>nr;
        f1>>x;
        lista[nr-1].insert(x);
    }
    if (y==2)
    {
        int nr;
        f1>>nr;
        f2<<lista[nr-1].extractMax()->key<<endl;
    }
    if(y==3)
    {
        int a;
        int b;
        f1>>a;
        f1>>b;
        lista[a-1].merge(lista[b-1]);

    }

        Q--;
}


    return 0;

}