众所周知，圆方树是用来处理图上点双相关问题的。
同时，点双又是一个和简单路径密切相关的东西。故而这一题我们可以考虑用圆方树来处理。
我们发现，如果两点之间有多条简单路径，那么它们一定处于同一个点双中。所以，我们可以把原图转化为圆方树，这样就可以用树链剖分套线段树来求解询问了。
但是题目要求要修改点权，这要怎么办呢？
一个直观的想法是暴力修改每个点周围相邻的方点。然而事实上如果出现了个菊花套菊花套菊花图的话显然是会严重TLE的。
我们考虑一种动态维护一个方点的点值的算法。我们尝试对每个方点开一个mulitiset，每当修改一个点的点权的时候就把旧的点权删去然后插入新的点权，并更新方点点值。
然而，如果每个修改的圆点周围都有很多的方点的话，这种做法仍然有TLE的风险。我们考虑对于每个圆点，只更新它的父亲方点。
它对它的儿子方点的贡献，则在询问的时候统计。
这样复杂度就对了。
这就使用了圆方树上树链剖分套线段树解决了这道题。
注意：
树链剖分中更新最大孩子的部分，这里是son！不是sz！调了我一个晚上！
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)
std::multiset<int> s[200005];
const int INF=2147483647;
inline int Max(int A,int B){
return A>B?A:B;
}
inline int Min(int A,int B){
return A<B?A:B;
}
inline void Swap(int &A,int &B){
A^=B^=A^=B;
}
struct ee{
int v;
int nxt;
}e[2000005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
e[++et]=(ee){V,H[U]};
H[U]=et;
}
inline void add(int *H,int U,int V){
Eadd(H,U,V);
Eadd(H,V,U);
}
int dfn[200005],lw[100005];
//注意数组大小。
int nm,cnt=0;
int st[100005],tp=0;
inline void dfs0(int X){
dfn[X]=lw[X]=++cnt;
st[++tp]=X;
Fv(h0,i,X){
if(!dfn[e[i].v]){
dfs0(e[i].v);
lw[X]=Min(lw[X],lw[e[i].v]);
if(lw[e[i].v]==dfn[X]){
++nm;
for(int j=0;j!=e[i].v;--tp){
j=st[tp];
add(h,nm,j);
}
add(h,X,nm);
}
}else{
lw[X]=Min(lw[X],dfn[e[i].v]);
}
}
}
int fa[200005],sz[200005],dep[200005],son[200005],top[200005],loc[200005];
inline void dfs1(int X,int FA){
fa[X]=FA,dep[X]=dep[FA]+1,sz[X]=1;
Fv(h,i,X){
if(e[i].v!=FA){
dfs1(e[i].v,X);
sz[X]+=sz[e[i].v];
if(sz[son[X]]<sz[e[i].v]){
son[X]=e[i].v;
//这里是son！不是sz！调了我一个晚上！
}
}
}
}
inline void dfs2(int X,int FA,int TP){
dfn[X]=++cnt,loc[cnt]=X,top[X]=TP;
if(son[X]){
dfs2(son[X],X,TP);
}
Fv(h,i,X){
if(e[i].v!=FA&&e[i].v!=son[X]){
dfs2(e[i].v,X,e[i].v);
}
}
}
int n,m,q;
int a[200005];
#define MID (L+R>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[600005];
inline void bld(int X,int L,int R){
if(L==R){
tr[X]=a[loc[L]];
// 记得逆哈希
return;
}
bld(LS,L,MID);
bld(RS,MID+1,R);
tr[X]=Min(tr[LS],tr[RS]);
}
inline void chg(int X,int L,int R,int P,int V){
if(L==R){
tr[X]=V;
return;
}
P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
tr[X]=Min(tr[LS],tr[RS]);
}
inline int qry(int X,int L,int R,int A,int B){
if(A>R||L>B){
return INF;
}
if(A<=L&&R<=B){
return tr[X];
}
return Min(qry(LS,L,MID,A,B),qry(RS,MID+1,R,A,B));
}
void init(){
scanf("%d%d%d",&n,&m,&q);
nm=n;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int u,v;
for(int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
add(h0,u,v);
}
dfs0(1);
dfs1(1,0);
cnt=0;
dfs2(1,0,1);
for(int i=1;i<=n;++i){
if(fa[i]){
s[fa[i]].insert(a[i]);
}
}
for(int i=n+1;i<=nm;++i){
a[i]=*s[i].begin();
}
bld(1,1,nm);
char ch[3];
int x,y;
int ans;
for(int i=1;i<=q;++i){
scanf("%s%d%d",ch,&x,&y);
if(ch[0]=='C'){
chg(1,1,nm,dfn[x],y);
if(fa[x]){
u=fa[x];
s[u].erase(s[u].lower_bound(a[x]));
s[u].insert(y);
if(a[u]!=*s[u].begin()){
a[u]=*s[u].begin();
chg(1,1,nm,dfn[u],a[u]);
}
}
a[x]=y;
}else{
ans=INF;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
Swap(x,y);
}
ans=Min(ans,qry(1,1,nm,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(dfn[x]>dfn[y]){
Swap(x,y);
}
ans=Min(ans,qry(1,1,nm,dfn[x],dfn[y]));
if(x>n){
ans=Min(ans,a[fa[x]]);
}
printf("%d\n",ans);
}
}
}
int main(){
init();
return 0;
}
