← 返回题目列表

Codeforces · 487/E

E. 游客

中文机器翻译题面 查看原题

Cyber​​land中有n个城市,编号从1到n,由m条双向道路连接。第 j 条路连接 aj 市和 bj 市。

对于游客来说,赛博兰的每个城市都出售纪念品。特别是,city i 以 wi 的价格出售。

现在有 q 个查询需要您处理。有两种类型的查询:

- “C a w”:a城市的价格改为w。
- “A a b”:现在一名游客将从城市a前往城市b。他会选择一条路线,他也不想去一个城市两次。他会在纪念品最便宜的城市购买纪念品(可能正好在a城市或b城市)。你应该输出他在旅行期间可以购买纪念品的最低可能价格。

更正式地说,我们可以定义路由如下:

- 路线是一系列城市 [x1, x2, ..., xk],其中 k 是某个正整数。
- 对于任意 1 ≤ i < j ≤ k, xi ≠ xj。
- 对于任意 1 ≤ i < k,存在一条连接 xi 和 xi + 1 的道路。
- 路线的最低价格为 min(wx1, wx2, ..., wxk)。
- 所需答案是从 a 到 b 的所有有效路线的最低价格中的最小值。

输入

输入的第一行包含三个整数 n, m, q (1 ≤ n, m, q ≤ 105),用一个空格分隔。

接下来的 n 行包含整数 wi (1 ≤ wi ≤ 109)。

接下来 m 行包含一对空格分隔的整数 aj 和 bj (1 ≤ aj, bj ≤ n, aj ≠ bj)。

保证最多有一条道路连接同一对城市。任意两个城市之间始终至少有一条有效路线。

接下来的 q 行每行描述一个查询。格式为“C a w”或“A a b”(1 ≤ a、b ≤ n、1 ≤ w ≤ 109)。

输出

对于每个“A”类型的查询,输出相应的答案。

示例

输入 #1

3 3 3
1
2
3
1 2
2 3
1 3
A 2 3
C 1 5
A 2 3

输出 #1

1
2

输入 #2

7 9 4
1
2
3
4
5
6
7
1 2
2 5
1 5
2 3
3 4
2 4
5 6
6 7
5 7
A 2 3
A 6 4
A 6 7
A 3 3

输出 #2

2
1
5
3

注意

对于第二个样本,最佳路线是:

从2到3是[2, 3]。

从6到4是[6,5,1,2,4]。

从6到7是[6,5,7]。

从3到3是[3]。