/*
    Implementarea unui Pairing Heap. (max heap)
    Link pb. pe infoarena: https://infoarena.ro/problema/mergeheap

    Pairing Heap este o varianta de Heap in care fiecare nod contine 3 informatii:
        -un pointer la fiul stang
        -un pointer la frate
        -valoarea lui 
*/
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");

class Node {
private:
    Node* leftChild;
    Node* brother;
    int val;

public:
    Node() : leftChild(nullptr), brother(nullptr), val(-1) {};
    Node(int v, Node* left = nullptr, Node* bro = nullptr) : leftChild(left), brother(bro), val(v) {};

    int getVal() {
        return val;
    }

    Node* getLeftChild() {
        return leftChild;
    }

    void setLeftChild(Node* left) {
        leftChild = left;
    }

    Node* getBrother() {
        return brother;
    }

    void setBrother(Node* bro) {
        brother = bro;
    }

    void addChild(Node* heap) {
        if(leftChild == nullptr) 
            leftChild = heap;
        else {
            heap->setBrother(leftChild);
            leftChild = heap;
        }
    }

    ~Node() {
        delete leftChild;
        delete brother;
    }
};

Node* merge(Node* a, Node* b) {
        if(a == nullptr) return b;
        if(b == nullptr) return a;

        if( a->getVal() > b->getVal() ) {
            a->addChild(b);
            return a;
        } else {
            b->addChild(a);
            return b;
        }

        return nullptr;
}

Node* insert(Node* a, int val_) {
    return merge(a, new Node(val_));
}

int top(Node* a) {
    return a->getVal();
}

Node* createNewHeap(Node* a) {
    if( a == nullptr || a->getBrother() == nullptr )
        return a;
    else {
        Node* first = a;
        Node* second = a->getBrother();
        Node* maybe = a->getBrother()->getBrother();

        first->setBrother(nullptr);
        second->setBrother(nullptr);

        return merge( merge(first, second), createNewHeap(maybe) );
    }
}

Node* remove(Node* root) {
    return createNewHeap(root->getLeftChild());
}

vector<Node*> v;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q, op, val1, val2;
    fin >> n >> q;
    v.resize(n + 2);

    for(int i = 0; i < q; i++) {
        fin >> op >> val1;
        if( op != 2 ) fin >> val2;

        if( op == 1 ) {
            v[val1] = insert(v[val1], val2);
        } else if( op == 2 ) {
            fout << top(v[val1]) << '\n';
            v[val1] = remove(v[val1]);
        } else {
            v[val1] = merge(v[val1], v[val2]);
            v[val2] = nullptr;
        }
    }

    return 0;
}