#include <cmath>
#include <fstream>
#include <vector>
#include <limits>
#include <unordered_map>

using namespace std;
ifstream f("mergeheap.in");
ofstream g("mergeheap.out");

struct Node {
    int key;
    Node* parent;
    Node* child;
    Node* left;
    Node* right;
    int degree;
    bool marked;

    Node(int val) : key(val), parent(nullptr), child(nullptr), left(this), right(this), degree(0), marked(false) {}
};

class FibonacciHeap {
private:
    Node* max;
    int n;
    std::unordered_map<int, Node*> degreeTable;

    void consolidate();
    void link(Node* y, Node* x);
    void cut(Node* x, Node* y);
    void cascadingCut(Node* y);
    void removeFromRootList(Node* node);

public:
    FibonacciHeap() : max(nullptr), n(0) {}

    ~FibonacciHeap() {

    }

    void insert(int key);
    void merge(FibonacciHeap& other);
    int extractMax();
    void decreaseKey(Node* x, int k);
    int findMax() const {
        return max ? max->key : std::numeric_limits<int>::min();
    }
    bool isEmpty() const {
        return max == nullptr;
    }
};

void FibonacciHeap::insert(int key) {
    Node* newNode = new Node(key);
    if (max == nullptr) {
        max = newNode;
    } else {
        max->left->right = newNode;
        newNode->right = max;
        newNode->left = max->left;
        max->left = newNode;
        if (newNode->key > max->key) {
            max = newNode;
        }
    }
    n++;
}

void FibonacciHeap::merge(FibonacciHeap& other) {
    if (other.max == nullptr) return;
    if (max == nullptr) {
        max = other.max;
        n = other.n;
        return;
    }
    Node* temp = max->right;
    max->right = other.max->right;
    max->right->left = max;
    other.max->right = temp;
    other.max->right->left = other.max;

    if (other.max->key > max->key) {
        max = other.max;
    }
    n += other.n;
}

int FibonacciHeap::extractMax() {
    if (max == nullptr) return std::numeric_limits<int>::min(); // Heap is empty.

    Node* oldMax = max;
    int ret = oldMax->key;


    Node* tmpChild = oldMax->child;
    if (tmpChild != nullptr) {
        do {
            tmpChild->parent = nullptr;
            tmpChild = tmpChild->right;
        } while (tmpChild != oldMax->child);


        Node* maxLeft = max->left;
        Node* childLeft = oldMax->child->left;

        maxLeft->right = oldMax->child;
        oldMax->child->left = maxLeft;
        childLeft->right = max;
        max->left = childLeft;
    }


    removeFromRootList(oldMax);

    if (oldMax == oldMax->right) {
        max = nullptr;
    } else {
        max = oldMax->right;
        consolidate();
    }

    n--;
    delete oldMax;
    return ret;
}

void FibonacciHeap::removeFromRootList(Node* node) {
    node->left->right = node->right;
    node->right->left = node->left;
}

void FibonacciHeap::consolidate() {
    std::vector<Node*> A;
    A.resize(45);

    Node* start = max;
    Node* current = max;
    do {
        Node* x = current;
        current = current->right;
        int d = x->degree;
        while (A[d] != nullptr) {
            Node* y = A[d];
            if (x->key < y->key) {
                std::swap(x, y);
            }
            if (y == start) {
                start = start->right;
            }
            if (y == current) {
                current = y->right;
            }
            link(y, x);
            A[d] = nullptr;
            d++;
        }
        A[d] = x;
    } while (current != start);

    max = nullptr;
    for (int i = 0; i < A.size(); i++) {
        if (A[i] != nullptr) {
            if (max == nullptr) {
                max = A[i]->left = A[i]->right = A[i];
            } else {
                A[i]->left = max;
                A[i]->right = max->right;
                max->right = A[i];
                A[i]->right->left = A[i];
                if (A[i]->key > max->key) {
                    max = A[i];
                }
            }
        }
    }
}

void FibonacciHeap::link(Node* y, Node* x) {

    removeFromRootList(y);


    if (x->child == nullptr) {
        x->child = y;
        y->right = y;
        y->left = y;
    } else {
        y->left = x->child;
        y->right = x->child->right;
        x->child->right = y;
        y->right->left = y;
    }

    y->parent = x;
    x->degree++;
    y->marked = false;
}

int n,m,tip,x,y;
int main() {
    f>>n>>m;
    FibonacciHeap fh[n];
    while(m--)
    {
        f>>tip;
        if(tip==1)
        {
            f>>x>>y;
            fh[x-1].insert(y);
        }
        else
        if(tip==2)
        {
            f>>x;
            g<<fh[x-1].extractMax()<<'\n';
        }
        else
        {
            f>>x>>y;
            fh[x-1].merge(fh[y-1]);

        }
    }
    return 0;
}