3# 胖哥旅游(travel.cpp/c/pas)

3# 胖哥旅游(travel.cpp/c/pas)

Description

有 n 个景点,编号从 1 到 n。对所有景点,胖哥给他们做了一个排名。
景点之间由道路连接。若一个景点 a 可以通过若干个节点到另一个景点 b,则称这两个景点是连通的。
现在有两种操作:
B x y 表示在景点 x 与景点 y 之间修建一条道路。
Q x k 表示询问当前与景点 x 连通的所有景点中,排名第 k 的景点是哪个,请你输出那个景点的编号。

Format

Input

第一行两个正整数 n 和 m,分别表示景点的个数以及一开始存在的道路数。
接下来的一行有 n 个数,依次描述胖哥给景点 1 到景点 n 的排名(排名用 1 到 n 来表示)。
随后的 m 行每行两个正整数 a 和 b,表示一开始就存在一条连接景点 a 与景点 b 的道路。后面剩下的部分描述操作。
该部分的第一行是一个正整数 q,表示一共有 q 个操作。
接下来的 q 行依次描述每个操作,操作的格式如上所述,以大写字母 Q 或 B 开始,后面跟两个不超过 n 的正整数。

Output

对于每个 Q x k 操作都要依次输出一行,其中包含一个整数,表示所询问景点的编号。
如果该景点不存在,则输出-1。

Sample 1

Input

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

Output

-1
2
5
1
2

Limitation

1s, 256MiB for each test case.
【数据说明】
对于 30%的数据 n≤1000,q≤1000
对于 60%的数据 n≤10000,q≤10000
对于 100%的数据 n≤100000,m≤n,q≤300000

Source

2018年泉州复赛模拟提高组 day3t3