CF487E Tourists

There are $ n $ cities in Cyberland, numbered from $ 1 $ to $ n $ , connected by $ m $ bidirectional roads. The $ j $ -th road connects city $ a_{j} $ and $ b_{j} $ . For tourists, souvenirs are sold in every city of Cyberland. In particular, city $ i $ sell it at a price of $ w_{i} $ . Now there are $ q $ queries for you to handle. There are two types of queries: - "C $ a $ $ w $ ": The price in city $ a $ is changed to $ w $ . - "A $ a $ $ b $ ": Now a tourist will travel from city $ a $ to $ b $ . He will choose a route, he also doesn't want to visit a city twice. He will buy souvenirs at the city where the souvenirs are the cheapest (possibly exactly at city $ a $ or $ b $ ). You should output the minimum possible price that he can buy the souvenirs during his travel. More formally, we can define routes as follow: - A route is a sequence of cities $ \[x_{1},x_{2},...,x_{k}\] $ , where $ k $ is a certain positive integer. - For any $ 1

The first line of input contains three integers $n, m, q (1 \leq n, m, q \leq 10^5)$, separated by a single space. Next n lines contain integers $w_i (1 \leq w_i \leq 10^9)$. Next m lines contain pairs of space-separated integers $a_j$ and $b_j$ $(1 \leq a_j, b_j \leq n, aj \neq bj)$. It is guaranteed that there is at most one road connecting the same pair of cities. There is always at least one valid route between any two cities. Next $q$ lines each describe a query. The format is "C a w" or "A a b" $(1 \leq a, b \leq n, 1 \leq w \leq 10^9)$.

For each query of type "A", output the corresponding answer.

For the second sample, an optimal routes are: From 2 to 3 it is $[2, 3]$. From 6 to 4 it is $[6, 5, 1, 2, 4]$. From 6 to 7 it is $[6, 5, 7]$. From 3 to 3 it is $[3]$.