#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int bsize = 1 << 20;

class Buffer {
  public:
    Buffer() {
      refresh();
    }

    Buffer& operator>>(int &v) {
      while (!isDigit(data[pos]))
        if (++pos == bsize)
          refresh();

      v = 0;
      while (isDigit(data[pos])) {
        v = v * 10 + data[pos] - '0';
        if (++pos == bsize)
          refresh();
      }

      return *this;
    }

  private:
    char data[bsize];
    int pos;

    bool isDigit(char c) {
      return '0' <= c && c <= '9';
    }

    void refresh() {
      memset(data, 0, sizeof(data));
      fread(data, 1, bsize, stdin);
      pos = 0;
    }
};

struct Node {
  int value;
  Node *son, *sibling;

  Node(int _value) : value(_value), son(NULL), sibling(NULL) { };

  Node* link(Node *newSon) {
    newSon->sibling = son;
    son = newSon;
    return this;
  }
};

Node* merge(Node *n1, Node *n2) {
  if (n1 == NULL) return n2;
  if (n2 == NULL) return n1;

  if (n1->value > n2->value) {
    return n1->link(n2); 
  } else {
    return n2->link(n1);
  }
}

Node* push(Node *n, int v) {
  return merge(n, new Node(v));
}

Node* mergeNodes(Node *curr) {
  if (curr == NULL) return NULL;

  Node *nxt = curr->sibling;
  if (nxt == NULL) return curr;

  Node *after = nxt->sibling;
  Node *combo = merge(curr, nxt);
  return merge(combo, mergeNodes(after));
}

pair<int, Node*> pop(Node *n) {
  int ans = n->value;
  Node *rest = mergeNodes(n->son);

  delete n;
  return make_pair(ans, rest);
} 

int n, q, kind, a, b;
Node* node[111];
pair<int, Node*> ans;


int main()
{
  freopen("mergeheap.in", "r", stdin);
  freopen("mergeheap.out", "w", stdout);
  Buffer fin;

  fin >> n >> q;
  for (int i = 1; i <= q; i++) {
    fin >> kind >> a;
    switch (kind) {
      case 1: 
        fin >> b;
        node[a] = push(node[a], b);
        break;

      case 2:
        ans = pop(node[a]);
        node[a] = ans.second;
        cout << ans.first << '\n';
        break;

      case 3:
        fin >> b;
        node[a] = merge(node[a], node[b]);
        node[b] = NULL;
    }
  }




  return 0;
}