#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

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);

  scanf("%d%d", &n, &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &kind, &a); 
    switch (kind) {
      case 1: 
        scanf("%d", &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:
        scanf("%d", &b);
        node[a] = merge(node[a], node[b]);
        node[b] = NULL;
    }
  }




  return 0;
}