#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)
    {

        Node *c = del->copil;
        if (c != nullptr) //Todo: sterge parintele de la toti
        {
            c->frateSt->frateDr = del->frateDr;
            del->frateDr->frateSt = c->frateSt;
            c->frateSt = del;
            del->frateDr = c;
            c->parinte = nullptr;
            c->frateSt->parinte = nullptr;
        }
        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)
    {

        rootElem->frateDr->frateSt = x.rootElem->frateSt;
        x.rootElem->frateSt->frateDr = rootElem->frateDr;
        rootElem->frateDr = x.rootElem;
        x.rootElem->frateSt = 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)
        {
            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;
        }
        if (rootElem->valoare < rulaj->valoare)
        {
            rootElem = rulaj;
        }
        while (v[rulaj->grad] != nullptr)
        {
            if (v[rulaj->grad]->valoare > rulaj->valoare)
            {
                swap(rulaj, v[rulaj->grad]);
            }
            resolveConflictBetweenTwoParties(v, rulaj, v[rulaj->grad]);
        }
    }
    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++;
    }
    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++)
  {
    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;
    }
  }
}