// Operations on a Fibonacci heap in C++

#include <cmath>
#include <cstdlib>
#include <fstream>
#include <map>

using namespace std;

ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");

// Node creation
struct node
{
    int n;
    int degree;
    node *parent;
    node *child;
    node *left;
    node *right;
    char mark;

    char C;
};

// Implementation of Fibonacci heap
class FibonacciHeap
{
private:
    int nH;

    node *H;

public:
    node *InitializeHeap();
    int Fibonnaci_link(node *, node *, node *);
    node *Create_node(int);
    node *Insert(node *, node *);
    node *Union(node *, node *);
    node *Extract_Min(node *);
    int Consolidate(node *);
    int Display(node *);
    node *Find(node *, int);
    int Decrease_key(node *, int, int);
    int Delete_key(node *, int);
    int Cut(node *, node *, node *);
    int Cascase_cut(node *, node *);
    FibonacciHeap()
    {
        H = InitializeHeap();
    }
};

// Initialize heap
node *FibonacciHeap::InitializeHeap()
{
    node *np;
    np = NULL;
    return np;
}

// Create node
node *FibonacciHeap::Create_node(int value)
{
    node *x = new node;
    x->n = value;
    return x;
}

// Insert node
node *FibonacciHeap::Insert(node *H, node *x)
{
    x->degree = 0;
    x->parent = NULL;
    x->child = NULL;
    x->left = x;
    x->right = x;
    x->mark = 'F';
    x->C = 'N';
    if (H != NULL)
    {
        (H->left)->right = x;
        x->right = H;
        x->left = H->left;
        H->left = x;
        if (x->n < H->n)
            H = x;
    }
    else
    {
        H = x;
    }
    nH = nH + 1;
    return H;
}

// Create linking
int FibonacciHeap::Fibonnaci_link(node *H1, node *y, node *z)
{
    (y->left)->right = y->right;
    (y->right)->left = y->left;
    if (z->right == z)
        H1 = z;
    y->left = y;
    y->right = y;
    y->parent = z;

    if (z->child == NULL)
        z->child = y;

    y->right = z->child;
    y->left = (z->child)->left;
    ((z->child)->left)->right = y;
    (z->child)->left = y;

    if (y->n < (z->child)->n)
        z->child = y;
    z->degree++;
}

// Union Operation
node *FibonacciHeap::Union(node *H1, node *H2)
{
    node *np;
    node *H = InitializeHeap();
    H = H1;
    (H->left)->right = H2;
    (H2->left)->right = H;
    np = H->left;
    H->left = H2->left;
    H2->left = np;
    return H;
}

// Display the heap
int FibonacciHeap::Display(node *H)
{
    node *p = H;
    if (p == NULL)
    {
        fout << "Empty Heap" << endl;
        return 0;
    }
    fout << "Root Nodes: " << endl;

    do
    {
        fout << p->n;
        p = p->right;
        if (p != H)
        {
            fout << "-->";
        }
    }
    while (p != H && p->right != NULL);
    fout << endl;
}

// Extract min
node *FibonacciHeap::Extract_Min(node *H1)
{
    node *p;
    node *ptr;
    node *z = H1;
    p = z;
    ptr = z;
    if (z == NULL)
        return z;

    node *x;
    node *np;

    x = NULL;

    if (z->child != NULL)
        x = z->child;

    if (x != NULL)
    {
        ptr = x;
        do
        {
            np = x->right;
            (H1->left)->right = x;
            x->right = H1;
            x->left = H1->left;
            H1->left = x;
            if (x->n < H1->n)
                H1 = x;

            x->parent = NULL;
            x = np;
        }
        while (np != ptr);
    }

    (z->left)->right = z->right;
    (z->right)->left = z->left;
    H1 = z->right;

    if (z == z->right && z->child == NULL)
        H = NULL;

    else
    {
        H1 = z->right;
        Consolidate(H1);
    }
    nH = nH - 1;
    return p;
}

// Consolidation Function
int FibonacciHeap::Consolidate(node *H1)
{
    int d, i;
    float f = (log(nH)) / (log(2));
    int D = f;
    node *A[D];

    for (i = 0; i <= D; i++)
        A[i] = NULL;

    node *x = H1;
    node *y;
    node *np;
    node *pt = x;

    do
    {
        pt = pt->right;
        d = x->degree;

        while (A[d] != NULL)
        {
            y = A[d];
            if (x->n > y->n)
            {
                np = x;
                x = y;
                y = np;
            }

            if (y == H1)
                H1 = x;
            Fibonnaci_link(H1, y, x);
            if (x->right == x)
                H1 = x;
            A[d] = NULL;
            d = d + 1;
        }

        A[d] = x;
        x = x->right;

    }

    while (x != H1);
    H = NULL;
    for (int j = 0; j <= D; j++)
    {
        if (A[j] != NULL)
        {
            A[j]->left = A[j];
            A[j]->right = A[j];
            if (H != NULL)
            {
                (H->left)->right = A[j];
                A[j]->right = H;
                A[j]->left = H->left;
                H->left = A[j];
                if (A[j]->n < H->n)
                    H = A[j];
            }
            else
            {
                H = A[j];
            }
            if (H == NULL)
                H = A[j];
            else if (A[j]->n < H->n)
                H = A[j];
        }
    }
}

// Decrease Key Operation
int FibonacciHeap::Decrease_key(node *H1, int x, int k)
{
    node *y;
    if (H1 == NULL)
    {
        fout << "The Heap is Empty" << endl;
        return 0;
    }
    node *ptr = Find(H1, x);
    if (ptr == NULL)
    {
        fout << "Node not found in the Heap" << endl;
        return 1;
    }

    if (ptr->n < k)
    {
        fout << "Entered key greater than current key" << endl;
        return 0;
    }
    ptr->n = k;
    y = ptr->parent;
    if (y != NULL && ptr->n < y->n)
    {
        Cut(H1, ptr, y);
        Cascase_cut(H1, y);
    }

    if (ptr->n < H->n)
        H = ptr;

    return 0;
}

// Cutting Function
int FibonacciHeap::Cut(node *H1, node *x, node *y)
{
    if (x == x->right)
        y->child = NULL;
    (x->left)->right = x->right;
    (x->right)->left = x->left;
    if (x == y->child)
        y->child = x->right;
    y->degree = y->degree - 1;
    x->right = x;
    x->left = x;
    (H1->left)->right = x;
    x->right = H1;
    x->left = H1->left;
    H1->left = x;
    x->parent = NULL;
    x->mark = 'F';
}

// Cascade cut
int FibonacciHeap::Cascase_cut(node *H1, node *y)
{
    node *z = y->parent;
    if (z != NULL)
    {
        if (y->mark == 'F')
        {
            y->mark = 'T';
        }
        else

        {
            Cut(H1, y, z);
            Cascase_cut(H1, z);
        }
    }
}

// Search function
node *FibonacciHeap::Find(node *H, int k)
{
    node *x = H;
    x->C = 'Y';
    node *p = NULL;
    if (x->n == k)
    {
        p = x;
        x->C = 'N';
        return p;
    }

    if (p == NULL)
    {
        if (x->child != NULL)
            p = Find(x->child, k);
        if ((x->right)->C != 'Y')
            p = Find(x->right, k);
    }

    x->C = 'N';
    return p;
}

// Deleting key
int FibonacciHeap::Delete_key(node *H1, int k)
{
    node *np = NULL;
    int t;
    t = Decrease_key(H1, k, -5000);
    if (!t)
        np = Extract_Min(H);
    if (np != NULL)
        fout << "Key Deleted" << endl;
    else
        fout << "Key not Deleted" << endl;
    return 0;
}

int main()
{
    FibonacciHeap fh;

    fout << 1;

    std::map<int, node*> mapIDToPointer;

    int n, q, operatie, heapNumber, a, b;
    node *p, *H;

    fin >> n >> q;
    for(int index = 0; index < q; ++index)
    {
        fin >> operatie;

        if(operatie == 2)
        {
            fin >> heapNumber;

            if(mapIDToPointer.find(heapNumber) == mapIDToPointer.end()) // problema garanteaza ca vom gasi mereu id-ul in map, dar e mai bine sa testam
            {
                fout << "Aceasta multime nu a fost initializata inca";
            }
            else
            {
                p = fh.Extract_Min(mapIDToPointer[heapNumber]);
                fout << p->n << '\n';
            }
        }
        else
        {
            fin >> a >> b;

            if (operatie == 1)
            {
                if(mapIDToPointer.find(a) == mapIDToPointer.end())
                {
                    H = fh.InitializeHeap();
                    p = fh.Create_node(b);
                    H = fh.Insert(H, p);
                    fout<<"Got here";
                    mapIDToPointer[a] = H;
                }
                else
                {
                    p = fh.Create_node(b);
                    H = fh.Insert(mapIDToPointer[a], p);
                }
            }
            else
            {
                if(mapIDToPointer.find(a) == mapIDToPointer.end() || mapIDToPointer.find(b) == mapIDToPointer.end())
                {
                    continue;
                }
                else
                {
                    H = fh.Union(mapIDToPointer[a], mapIDToPointer[b]);
                    mapIDToPointer.erase(b); /// in cazul uniunii de multimi, multimea a primeste toate elementele multimii b, iar multimea b devine vida;
                }
            }
        }
    }

}