Description

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.

Input Format

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

Output Format

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

5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

-1
2
5
1
2

Hint

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