#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include "assert.h"

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

pair<int, Node*> pop(Node *n) {
  assert(n != NULL);

  static vector<Node*> nodes;
  Node* curr = n->son;
  nodes.clear();

  const int ans = n->value;
  delete n;

  if (curr == NULL) 
    return make_pair(ans, (Node*) NULL);

  while (curr != NULL) {
    Node *nxt = curr->sibling;
    
    if (nxt == NULL) {
      nodes.push_back(curr);
      break;
    } else {
      Node *after = nxt->sibling;
      nodes.push_back(merge(curr, nxt));
      curr = after;
    }
  }

  curr = nodes[nodes.size() - 1];
  for (int i = nodes.size() - 2; i >= 0; i--) 
    curr = merge(curr, nodes[i]);

  return make_pair(ans, curr);
} 

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

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




  return 0;
}