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

N/A

N/A

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