永无乡 - 题目 - Universal Online Judge

题目描述

永无乡包含$n$座岛，编号从$1$到$n$，每座岛都有自己的独一无二的重要度，按照重要度可以将这$n$座岛排名，名次用$1$到$n$来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛$a$出发经过若干座（含$0$座）桥可以到达岛$b$，则称岛$a$和岛$b$是连通的。

现在有两种操作：

B x y 表示在岛$x$与岛$y$之间修建一座新桥。

Q x k 表示询问当前与岛$x$连通的所有岛中第$k$重要的是哪座岛，即所有与岛$x$连通的岛中重要度排名第$k$小的岛是哪座，请你输出那个岛的编号。

第一行是用空格隔开的两个整数，分别表示岛的个数$n$以及一开始存在的桥数$m$。

第二行有$n$个整数，第$i$个整数表示编号为$i$的岛屿的排名$p_i$。

接下来$m$行，每行两个整数$u, v$，表示一开始存在一座连接编号为$u$的岛屿和编号为$v$的岛屿的桥。

接下来一行有一个整数，表示操作个数$q$。

接下来$q$行，每行描述一个操作。每行首先有一个字符$op$，表示操作类型，然后有两个整数$x, y$。 - 若$op$为 Q，则表示询问所有与岛$x$连通的岛中重要度排名第$y$小的岛是哪座，请你输出那个岛的编号。 - 若$op$为 B，则表示在岛$x$与岛$y$之间修建一座新桥。

对于每个询问操作都要依次输出一行一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出$-1$。

对于$20\%$的数据，保证$n \leq 10^3$,$q \leq 10^3$。
对于$100\%$的数据，保证$1 \leq m \leq n \leq 10^5$,$1 \leq q \leq 3 \times 10^5$，$p_i$为一个$1 \sim n$的排列，$op \in { \texttt Q, \texttt B}$，$1 \leq u, v, x, \leq n$。