Description

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

Input Format

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

Output Format

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

5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2

1
2

Hint

【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