#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

class Node
{
public: // for speed
    bool areMark;
    int valoare;
    unsigned grad;
    Node *parinte;
    Node *copil;
    Node *frateSt;
    Node *frateDr;
    Node(bool areMark, int valoare, unsigned grad) : areMark(areMark), valoare(valoare), grad{grad}, parinte(nullptr), copil(nullptr), frateSt(nullptr), frateDr(nullptr){};
    Node(){};
};

class FibArbore
{
private:
    Node *rootElem;
    void appendRightTo(Node *toAdd, Node *init)
    {

        if (init == nullptr)
        {
            toAdd->frateDr = toAdd;
            toAdd->frateSt = toAdd;
            rootElem = toAdd;
            return;
        }

        toAdd->parinte = init->parinte;
        toAdd->frateDr = init->frateDr;
        toAdd->frateSt = init;
        init->frateDr->frateSt = toAdd;
        init->frateDr = toAdd;
        if (rootElem->valoare < toAdd->valoare)
        {
            rootElem = toAdd;
        }
    }
    void deleteNodeAndPromoteToRoot(Node *del)
    {

        if (del->copil != nullptr)
        {
            Node *ster = del->copil;
            ster->frateSt->frateDr = nullptr;
            Node *contor = del->copil->frateDr;
            while (contor != nullptr)
            {
                appendRightTo(ster, rootElem);
                ster = contor;
                contor = contor->frateDr;
            }
            appendRightTo(ster, rootElem);
        }
        del->frateSt->frateDr = del->frateDr;
        del->frateDr->frateSt = del->frateSt;
        delete del;
    }

public:
    int getMax()
    {
        int asd = rootElem->valoare;
        stergereRoot();
        return asd;
    }
    void insetElem(const int &x)
    {
        Node *a = new Node{0, x, 0};
        appendRightTo(a, rootElem);
    }
    void merge(FibArbore &x)
    {
        Node *rulment, *copias;
        rulment = x.rootElem->frateDr;
        copias = rulment->frateDr;
        while (rulment != x.rootElem)
        {
            appendRightTo(rulment, this->rootElem);
            rulment = copias;
            copias = copias->frateDr;
        }
        appendRightTo(x.rootElem, this->rootElem);

        if (x.rootElem->valoare > this->rootElem->valoare)
        {
            this->rootElem = x.rootElem;
        }
        x.rootElem = nullptr;
    }
    void stergereRoot()
    {
        vector<Node *> v(300001, nullptr);

        Node *viataNoua = rootElem->frateDr; // recalculam radacina dupa calamitate
        if (viataNoua == rootElem)
        {
            viataNoua = rootElem->copil;
            if (viataNoua == nullptr)
            {
                rootElem = nullptr;
                return;
            }
        }
        deleteNodeAndPromoteToRoot(rootElem);
        rootElem = viataNoua;
        Node *rulaj = viataNoua->frateDr;
        if (rulaj == nullptr)
        {
            return;
        }

        Node *tinMinte = rulaj->frateDr;
        while (rulaj != viataNoua)
        {
            // cout<<rulaj->valoare<<"  ";
            if (rootElem->valoare < rulaj->valoare)
            {
                rootElem = rulaj;
            }
            if (v[rulaj->grad] == nullptr)
            {
                v[rulaj->grad] = rulaj;
            }
            else
            {
                while (v[rulaj->grad] != nullptr)
                {
                    if (v[rulaj->grad]->valoare > rulaj->valoare)
                    {
                        swap(rulaj, v[rulaj->grad]);
                    }
                    resolveConflictBetweenTwoParties(v, rulaj, v[rulaj->grad]);
                }
                v[rulaj->grad] = rulaj;
            }

            rulaj = tinMinte;
            tinMinte = tinMinte->frateDr;
        }
        while (v[rulaj->grad] != nullptr)
        {
            // cout<<rulaj->valoare<<"  ";
            if (v[rulaj->grad]->valoare > rulaj->valoare)
            {
                swap(rulaj, v[rulaj->grad]);
            }
            resolveConflictBetweenTwoParties(v, rulaj, v[rulaj->grad]);
        }
        // cout << "\n\n ******* " << rootElem->valoare << " *******\n\n";
    }
    void resolveConflictBetweenTwoParties(vector<Node *> &v, Node *a, Node *b)
    {
        b->frateSt->frateDr = b->frateDr; // scoatem nodul mai mic din viata publica
        b->frateDr->frateSt = b->frateSt;
        if (a->copil == nullptr)
        {
            a->copil = b;
            b->frateDr = b;
            b->frateSt = b;
        }
        else
        {
            appendRightTo(b, a->copil);
        }

        b->parinte = a;
        v[a->grad] = nullptr;
        a->grad++;
    }
    void print()
    {
        if (rootElem != nullptr)
        {
            cout << rootElem->valoare << "  ";
            Node *a = rootElem->frateDr;
            while (a != rootElem)
            {
                cout << a->valoare << "  ";
                a = a->frateDr;
            }
        }
        else
            cout << " E gol \n\n";
        cout << "\n"
             << endl;
    }
    FibArbore() : rootElem{nullptr} {}

};
vector<FibArbore> v;
int main()
{
  // TO DO: Reprodu seg fault;
  int n, q, op, elem, m;
  ifstream cin("mergeheap.in");
  ofstream cout("mergeheap.out");
  cin >> n >> q;
  v.resize(n);
  for (size_t i = 0; i < q; i++)
  {
    // cout << "i: " << i << '\n';
    cin >> op >> m;
    m--;
    switch (op)
    {
    case 1:
      cin >> elem;
      v[m].insetElem(elem);
      break;

    case 3:
      cin >> elem;
      elem--;
      v[m].merge(v[elem]);

      break;

    default:

      cout << v[m].getMax() << '\n';

      break;
    }
  }
}