#pragma GCC optimize("O3")
#define NDEBUG
#include <vector>
#include <cstdint>
#include <cassert>
#include <string>
#include <algorithm>
namespace ja::AdvancedDataStructures::FibonacciHeap {
#ifndef jassert
#define jassert(expr, msg, ...) assert(expr && msg)
#endif // jassert
#ifndef jlog
#define jlog(...) ((void)0)
#endif // jlog
template < typename DATA, typename OPS >
class FibonacciHeap {
public:
struct Node { // This has to be public, since it's also the index for decrease_key()
DATA key; int32_t degree; bool mark;
Node *left, *right, *parent, *child;
Node(const DATA& _value) {
key = _value; degree = 0; mark = false;
left = right = this;
parent = child = nullptr;
}
};
private:
Node *heap_min;
size_t node_count;
OPS op{};
void _erase(Node *a) {
if(a == nullptr) return;
for(Node *b = a->right; b != a;) {
_erase(b->child);
Node *next_b = b->right;
delete b;
b = next_b;
}
_erase(a->child); delete a;
}
Node* _merge(Node *a, Node *b) {
if(a == nullptr || b == nullptr) return (a ? a : b);
if( op.less(b->key, a->key) ) std::swap(a, b); // Make sure you have to merge b into a (a remains heap_min)
// Connect the two circular lists
Node *a_right = a->right, *b_left = b->left;
a->right = b; b->left = a;
a_right->left = b_left; b_left->right = a_right;
return a;
}
void _extract_from_circular_list(Node *node) {
if(node->right == node) return;
Node *l = node->left, *r = node->right;
l->right = r; r->left = l;
node->left = node->right = node;
}
void _insert_node(Node *new_node) {
heap_min = _merge(heap_min, new_node);
}
void _remove_parents_from_circular_list(Node *node) {
if(node == nullptr) return; // there is no element in the circular list
Node *oth = node;
do { oth->parent = nullptr; oth = oth->right; } while(oth != node);
}
Node* _add_child(Node *parent, Node *child) {
if( op.less(child->key, parent->key) ) std::swap(parent, child);
parent->degree += 1;
parent->child = _merge(parent->child, child);
child->parent = parent;
return parent;
}
DATA _get_min() {
return heap_min->key;
}
void _consolidate() {
const int MAX_DEGREE = 24; int max_degree = 0;
static Node* root_by_degree[MAX_DEGREE] = {nullptr,};
if(heap_min == nullptr) return; // nothing to consolidate
Node *to_consolidate;
bool more_to_consolidate = true;
do {
to_consolidate = heap_min->right;
_extract_from_circular_list(to_consolidate);
if(to_consolidate == heap_min) more_to_consolidate = false;
for(int deg = to_consolidate->degree; deg < MAX_DEGREE; deg += 1) {
if(deg > max_degree) max_degree = deg;
if(root_by_degree[deg] == nullptr) {
root_by_degree[deg] = to_consolidate;
break;
}
else {
to_consolidate = _add_child(to_consolidate, root_by_degree[deg]);
root_by_degree[deg] = nullptr;
}
}
} while(more_to_consolidate);
heap_min = nullptr;
for(int deg = max_degree; deg >= 0; deg -= 1) {
heap_min = _merge(heap_min, root_by_degree[deg]);
root_by_degree[deg] = nullptr;
}
}
void _pop_min() {
if(heap_min->right == heap_min) { // |Roots| has one element, special case
Node *new_heap_min = heap_min->child;
_remove_parents_from_circular_list(heap_min->child);
delete heap_min;
heap_min = new_heap_min;
return;
}
Node *heap_min_children = heap_min->child;
Node *new_heap_min = heap_min->right;
// break links to other nodes on its level
_extract_from_circular_list(heap_min);
// before deleting
delete heap_min;
_remove_parents_from_circular_list(heap_min_children);
heap_min = _merge(new_heap_min, heap_min_children);
_consolidate();
}
void _cut(Node *node) {
node->mark = false; // Mark it, since it has been cut
// Break links to parent and siblings
if(node->right == node) node->parent->child = nullptr;
else node->parent->child = node->right;
node->parent->degree -= 1;
_extract_from_circular_list(node);
node->parent = nullptr;
// Add it to |Roots|
heap_min = _merge(heap_min, node);
}
void _cascut(Node *node) { // cascading cut
if(node->parent == nullptr) {
node->mark = false;
return;
}
if(node->mark == false) {
node->mark = true;
}
else {
Node *parent = node->parent;
_cut(node); _cascut(parent);
}
}
void _decrease_key(Node *node, const DATA& new_key) {
node->key = new_key;
if(node->parent == nullptr) {
if( op.less(node->key, heap_min->key) ) heap_min = node;
}
else {
Node *parent = node->parent;
_cut(node); _cascut(parent);
}
}
public:
struct Iterator {
// private:
Node *node_ptr;
// public:
Iterator() { node_ptr = nullptr; }
Iterator(Node *_node_ptr) { node_ptr = _node_ptr; }
DATA value() { return node_ptr->key; }
};
FibonacciHeap() {
heap_min = nullptr; node_count = 0;
}
void clear() { node_count = 0; _erase(heap_min); heap_min = nullptr; }
size_t size() { return node_count; }
Iterator insert(const DATA &v) {
node_count += 1;
Node *v_node = new Node(v);
heap_min = _merge(heap_min, v_node);
return Iterator(v_node);
}
DATA get_min() {
jassert(heap_min != nullptr, "heap must not be empty", heap_min);
return _get_min();
}
void pop_min() {
jassert(heap_min != nullptr, "heap must not be empty", heap_min);
node_count -= 1; _pop_min();
}
void decrease_key(Iterator it, const DATA& new_key) {
jassert( !op.less(it.value(), new_key), "New key must be less than old key", new_key, it.value());
_decrease_key(it.node_ptr, new_key);
}
void decrease_key_if_smaller(Iterator it, const DATA& new_key) {
if( op.less(new_key, it.node_ptr->key) ) _decrease_key(it.node_ptr, new_key);
}
void erase(Iterator it) {
jassert(heap_min != nullptr, "heap must not be empty", heap_min);
node_count -= 1;
_decrease_key(it.node_ptr, op.min());
_pop_min();
}
void join(FibonacciHeap& oth) {
node_count += oth.node_count;
heap_min = _merge(heap_min, oth.heap_min);
oth.heap_min = nullptr; oth.node_count = 0;
}
};
};
#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
ifstream in("mergeheap.in");
ofstream out("mergeheap.out");
#define cin in
#define cout out
#endif // INFOARENA
struct ops {
int32_t min() { return -1e9; }
bool less(int32_t a, int32_t b) { return a > b; }
};
ja::AdvancedDataStructures::FibonacciHeap::FibonacciHeap<int32_t, ops> v[105];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
for(int i = 0; i < q; i++) {
int t; cin >> t;
if(t == 1) {
int m, x; cin >> m >> x;
v[m].insert(x);
}
if(t == 2) {
int m; cin >> m;
cout << v[m].get_min() << '\n';
v[m].pop_min();
}
if(t == 3) {
int a, b; cin >> a >> b;
v[a].join(v[b]);
}
}
}