P3377 【Template】Meldable Heap 1

As stated, initially there are $n$ min-heaps, each containing exactly one number. Afterwards, you need to support two types of operations: 1. `1 x y`: Merge the min-heap containing the $x$-th number and the min-heap containing the $y$-th number (if the $x$-th or $y$-th number has already been deleted, or if the $x$-th and $y$-th numbers are in the same heap, ignore this operation). 2. `2 x`: Output the minimum number in the heap containing the $x$-th number, and delete this minimum number (if there are multiple minimum numbers, delete the one that was inserted earlier; if the $x$-th number has already been deleted, output $-1$ and ignore the deletion).

The first line contains two positive integers $n, m$, representing the initial number of min-heaps and the number of subsequent operations, respectively. The second line contains $n$ positive integers, where the $i$-th integer is the only number initially contained in the $i$-th min-heap. Each of the next $m$ lines contains $2$ or $3$ positive integers, representing one operation in the following formats: Operation 1: `1 x y` Operation 2: `2 x`

The output contains several lines of integers, each corresponding to the result of an operation of type `2`, in order.

【Constraints】 For $30\%$ of the testdata: $n \le 10$, $m \le 10$. For $70\%$ of the testdata: $n \le 10^3$, $m \le 10^3$. For $100\%$ of the testdata: $n \le 10^5$, $m \le 10^5$, and all initial numbers in the min-heaps are within the `int` range. 【Sample Explanation】 Initially, the five min-heaps are: $\{1\}$, $\{5\}$, $\{4\}$, $\{2\}$, $\{3\}$. In the first operation, merge the heap containing the $1$-st number with the heap containing the $5$-th number, resulting in four min-heaps: $\{1,3\}$, $\{5\}$, $\{4\}$, $\{2\}$. In the second operation, merge the heap containing the $2$-nd number with the heap containing the $5$-th number, resulting in three min-heaps: $\{1,3,5\}$, $\{4\}$, $\{2\}$. In the third operation, output and delete the minimum of the heap containing the $2$-nd number, so output $1$; the first number is deleted, and the three min-heaps become: $\{3,5\}$, $\{4\}$, $\{2\}$. In the fourth operation, merge the heap containing the $4$-th number with the heap containing the $2$-nd number, resulting in two min-heaps: $\{2,3,5\}$, $\{4\}$. In the fifth operation, output and delete the minimum of the heap containing the $2$-nd number, so output $2$; the fourth number is deleted, and the two min-heaps become: $\{3,5\}$, $\{4\}$. Therefore, the outputs are $1$ and $2$ in order. Translated by ChatGPT 5