P3224 [HNOI2012] Neverland

Neverland contains $n$ islands, numbered from $1$ to $n$. Each island has its own unique importance. According to importance, these $n$ islands can be ranked, with ranks from $1$ to $n$. Some islands are connected by large bridges, through which one can travel from one island to another. If starting from island $a$ you can reach island $b$ after crossing several (including $0$) bridges, then islands $a$ and $b$ are said to be connected. There are two operations: `B x y` means building a new bridge between island $x$ and island $y$. `Q x k` asks which island currently ranks the $k$-th by importance among all islands connected to island $x$, i.e., among all islands connected to $x$, which island has the $k$-th smallest importance rank. Please output the index of that island.

The first line contains two integers separated by a space, representing the number of islands $n$ and the initial number of bridges $m$. The second line contains $n$ integers; the $i$-th integer is the rank $p_i$ of island $i$. The next $m$ lines each contain two integers $u, v$, indicating that initially there is a bridge connecting island $u$ and island $v$. The next line contains an integer, the number of operations $q$. The next $q$ lines each describe an operation. Each line first contains a character $op$ indicating the operation type, followed by two integers $x, y$. - If $op$ is `Q`, it asks which island ranks the $y$-th smallest by importance among all islands connected to $x$; output the index of that island. - If $op$ is `B`, it means building a new bridge between island $x$ and island $y$.

For each query operation, output one integer on a separate line, indicating the index of the island being asked for. If such an island does not exist, output $-1$.

### Constraints - For $20\%$ of the testdata, $n \leq 10^3$, $q \leq 10^3$. - For $100\%$ of the testdata, $1 \leq m \leq n \leq 10^5$, $1 \leq q \leq 3 \times 10^5$, $p$ is a permutation of $1 \sim n$, $op \in \{\texttt Q, \texttt B\}$, $1 \leq u, v, x, y \leq n$. Translated by ChatGPT 5