/*
This code describes the behaviour of a Fibonacci Heap using a doubly linked list (that is not circular) as a root list. All other methods are kept canonical and one can read them on wikipedia for a better intuitive explanation.

Author: Lupascu Miruna-Stefania
*/

#include <fstream>
#include <map>
using namespace std;

ifstream cin("mergeheap.in");
ofstream cout("mergeheap.out");

struct node{
    node *left = NULL, *right = NULL, *father = NULL, *child = NULL;
    int info = 0, numberOfChildren = 0;
    bool marked = false;
};

//This class is not static, each instance represents a set in our problem.
class FibonacciHeap{

public:
    node *pointerToMax = NULL, *pointerToRoot = NULL, *pointerToEnd = NULL;
    void initialise(int newNodeInfo);
    void insert(int newNodeInfo);
    void unionOfHeaps(FibonacciHeap otherSet);
    int extractMax();
    void combine();
    void decreseKey();
    void deleteKey();
};

void FibonacciHeap::initialise(int newNodeInfo){
    node *newNode = new node();
    newNode->info = newNodeInfo;

    this->pointerToMax = newNode;
    this->pointerToRoot = newNode;
    this->pointerToEnd = newNode;
}

//This method has an output parameter through rootNode (so the value will be changed and we don't need to return something)
void FibonacciHeap::insert(int newNodeInfo){
    node *newNode = new node();

    newNode->right = this->pointerToRoot;
    this->pointerToRoot->left = newNode;
    newNode-> info = newNodeInfo;
    this->pointerToRoot = newNode;

    if(newNodeInfo > this->pointerToMax->info){
        this->pointerToMax = newNode;
    }
}

//This method performs the union of two heaps by merging their root lists. The first parameter is also an output parameter, thus respecting the specifiations of the problem
void FibonacciHeap::unionOfHeaps(FibonacciHeap otherSet){
    //We tie the starts of the lists between each other and update the start to be the end of the this heap

    this->pointerToEnd->right = otherSet.pointerToRoot;
    otherSet.pointerToRoot->left = this->pointerToEnd;

    this->pointerToEnd = otherSet.pointerToEnd;

    if(this->pointerToMax->info < otherSet.pointerToMax->info){
        this->pointerToMax = otherSet.pointerToMax;
    }

}

//This method extracts the maximum from the heap and modifies the shape of the whole set by combining roots with the same degree (the same number of children)
int FibonacciHeap::extractMax(){
    //We need to extract the current max, then delete the node and place all of its children in the root list
    bool missingRight = false, missingLeft = false;
    node *auxNode;
    int maxElem = this->pointerToMax->info;

    //redo the linking in the root chain
    if(this->pointerToMax->left != NULL || this->pointerToMax->right != NULL){
        if(this->pointerToMax == this->pointerToEnd){
            this->pointerToEnd = this->pointerToEnd->left;        
        }
        
        if(this->pointerToMax == this->pointerToRoot){
            this->pointerToRoot = this->pointerToRoot->right;
        }

        if(this->pointerToMax->left == NULL){
            this->pointerToMax->left = new node();
            missingLeft = true;
        }

        if(this->pointerToMax->right == NULL){
            this->pointerToMax->right = new node();
            missingRight = true;
        }

        this->pointerToMax->left->right = this->pointerToMax->right;
        this->pointerToMax->right->left = this->pointerToMax->left;

        if(missingLeft){
            this->pointerToMax->left = NULL;
            this->pointerToMax->right->left = NULL;
        }

        if(missingRight){
        this->pointerToMax->right = NULL;
        this->pointerToMax->left->right = NULL;
    }
    }
    else{
        this->pointerToRoot = this->pointerToMax->child;
    }
    
    //now that we excluded the max from the chain, we need to add its children to the root chain
    if(this->pointerToMax->child != NULL){
        auxNode = this->pointerToMax->child;
        node *nextNode;

        while(auxNode!= NULL){
            nextNode = auxNode->right;
            auxNode->father = NULL;
            auxNode->left = NULL;
            auxNode->right = this->pointerToRoot;
            this->pointerToRoot->left = auxNode;
            this->pointerToRoot = auxNode;
            auxNode = nextNode;
        }
    }
    
    //Now we need to reduce the number of trees in the root chain
    FibonacciHeap::combine();

    //Once we reduced the number of trees, we need to go through the chain and find the max and the end
    auxNode = this->pointerToRoot;
    this->pointerToMax = this->pointerToRoot;

    while(auxNode->right != NULL){
        if(auxNode->info > this->pointerToMax->info){
            this->pointerToMax = auxNode;
        }
        auxNode = auxNode->right;
    }

    this->pointerToEnd = auxNode;
    if(auxNode->info > this->pointerToMax->info){
            this->pointerToMax = auxNode;
        }

    return maxElem;
}

//This method goes through the root chain and combines together sub-trees of same degree
void FibonacciHeap::combine(){
    node *auxNode = this->pointerToRoot;
    map<int, node*> mapDegreesToNode;

    while(auxNode){
        if(mapDegreesToNode.find(auxNode->numberOfChildren) != mapDegreesToNode.end() && mapDegreesToNode[auxNode->numberOfChildren] != auxNode){
            //This means we have at least 2 different nodes of the same degree, so we need to combine them

            if(auxNode->child){
                auxNode->child->left = mapDegreesToNode[auxNode->numberOfChildren];
                mapDegreesToNode[auxNode->numberOfChildren]->right = auxNode->child;
                mapDegreesToNode[auxNode->numberOfChildren]->father = auxNode;

                auxNode->child = mapDegreesToNode[auxNode->numberOfChildren];
                mapDegreesToNode.erase(auxNode->numberOfChildren-1);
                auxNode->numberOfChildren++;
                auxNode = this->pointerToRoot;
                continue;
            }
            else{
                auxNode->child = mapDegreesToNode[auxNode->numberOfChildren];
                mapDegreesToNode[auxNode->numberOfChildren]->father = auxNode;
                mapDegreesToNode.erase(auxNode->numberOfChildren);
                auxNode->numberOfChildren++;
                auxNode = this->pointerToRoot;
                continue;
            }
        }
        else{
            mapDegreesToNode[auxNode->numberOfChildren] = auxNode;
        }

        auxNode = auxNode->right;
    }

}


int main(){


    std::map<int, FibonacciHeap> mapIDToPointer;

    int n, q, operatie, heapNumber, a, b;
    FibonacciHeap *auxHeap;

    cin >> n >> q;

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

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

            // problema garanteaza ca vom gasi mereu id-ul in map, dar e mai bine sa testam
            if(mapIDToPointer.find(heapNumber) == mapIDToPointer.end()) {
                cout << "Aceasta multime nu a fost initializata inca";
            }
            else{
                auxHeap = &mapIDToPointer[heapNumber];

                cout << auxHeap->extractMax() << '\n';
            }
        }
        else{
            cin >> a >> b;
            if (operatie == 1){
                
                //if we don't have this set initialised, we initialise it
                if(mapIDToPointer.find(a) == mapIDToPointer.end()){
                    auxHeap = new FibonacciHeap();
                    auxHeap->initialise(b);
                    mapIDToPointer[a] = *auxHeap;
                }
                else{
                    mapIDToPointer[a].insert(b);
                }
            }
            else{
                if(mapIDToPointer.find(a) == mapIDToPointer.end() || mapIDToPointer.find(b) == mapIDToPointer.end()){
                    continue;
                }
                else{
                    mapIDToPointer[a].unionOfHeaps(mapIDToPointer[b]);
                    mapIDToPointer.erase(b);
                }
            }
        }
    }
    
}