use std::{collections::BinaryHeap, fs::File, io::{BufRead, BufReader, BufWriter, Write}};

#[derive(Debug, Clone)]
struct HeapFragment(BinaryHeap<u32>);

#[derive(Debug, Clone)]
struct PairingHeap {
    top: Option<u32>,
    sub_heaps: Vec<PairingHeap>
}


impl PairingHeap {
    fn max(&mut self) -> Option<u32> {
        let val = self.top.take();
        if !self.sub_heaps.is_empty() {
            let mut new_heap = self.sub_heaps.pop().unwrap();
            for other_heap in self.sub_heaps.drain(0..) {
                new_heap.merge(other_heap);
            }
            self.top = new_heap.top.take();
            self.sub_heaps = new_heap.sub_heaps;
        }
        val
    }
    fn merge(&mut self, mut other: PairingHeap) {
        if let Some(other_top) = other.top.take() {
            if self.top.is_none() {
                self.top = Some(other_top);
                self.sub_heaps = other.sub_heaps;
            } else {
                if self.top.unwrap() >= other_top {
                    self.sub_heaps.push(PairingHeap{top: Some(other_top), sub_heaps: other.sub_heaps});
                } else {
                    let old_top = self.top.take().unwrap();
                    self.top = Some(other_top);
                    self.sub_heaps.push(PairingHeap{top: Some(old_top), sub_heaps: vec![]});
                    self.sub_heaps.append(&mut other.sub_heaps);
                }
            }
        }
    }
    fn insert(&mut self, element: u32) {
        if self.top.is_none() {
            self.top = Some(element);
        } else if self.top.unwrap() < element {
            let old_top = self.top.take().unwrap();
            self.top = Some(element);
            self.sub_heaps.push(PairingHeap {top: Some(old_top), sub_heaps: vec![]});
        } else {
            self.sub_heaps.push(PairingHeap {top: Some(element), sub_heaps: vec![]});
        }
    }

}

fn main() {
    let mut input_file = BufReader::new(File::open("mergeheap.in").unwrap());
    let mut current_line = String::new();
    let _  = input_file.read_line(&mut current_line).unwrap();
    let (n, q) = current_line.trim().split_once(' ').unwrap();
    let n = n.parse::<u32>().unwrap();
    let q = q.parse::<u32>().unwrap();
    let mut ph: Vec<PairingHeap> = vec![PairingHeap {top: None, sub_heaps: vec![]}; n as usize];
    let mut out_file = BufWriter::new(File::create("mergeheap.out").unwrap());
    for _ in 0..q {
        current_line.clear();
        let _  = input_file.read_line(&mut current_line).unwrap();
        let (op, rest) = current_line.trim().split_once(' ').unwrap();
        match op {
            "1" => {
                let (m, x) = rest.split_once(' ').unwrap();
                let m = m.parse::<usize>().unwrap();
                let x = x.parse::<u32>().unwrap();
                ph[m - 1].insert(x);
            }
            "2" => {
                let m = rest.parse::<usize>().unwrap();                
                let val = ph[m - 1].max().unwrap();
                let _ = writeln!(out_file, "{val}").unwrap();
            }
            "3" => {
                let (a, b) = rest.split_once(' ').unwrap();
                let a = a.parse::<usize>().unwrap();
                let b = b.parse::<usize>().unwrap();
                let b = PairingHeap{ top: ph[b - 1].top.take(), sub_heaps: ph[b - 1].sub_heaps.drain(0..).collect()};
                ph[a - 1].merge(b);
            }
            _ => panic!("Unkown op {op}")
        }
    }
}