CF487E Tourists

Cyberland 有 $n$ 座城市，编号从 $1$ 到 $n$，有 $m$ 条双向道路连接这些城市。第 $j$ 条路连接城市 $a_j$ 和 $b_j$。每天，都有成千上万的游客来到 Cyberland 游玩。 在每一个城市，都有纪念品售卖，第 $i$ 个城市售价为 $w_i$。这个售价有时会变动。 每一个游客的游览路径都有固定起始城市和终止城市，且不会经过重复的城市。 他们会在路径上的城市中，售价最低的那个城市购买纪念品。 你能求出每一个游客在所有合法的路径中能购买的最低售价是多少吗？ 你要处理 $q$ 个操作： `C a w`： 表示 $a$ 城市的纪念品售价变成 $w$。 `A a b`： 表示有一个游客要从 $a$ 城市到 $b$ 城市，你要回答在所有他的旅行路径中最低售价的最低可能值。

无

无

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