若从 (x) 到 (y) 的任意一条路径经过了一个点双连通分量，则从 (x) 到 (y) 一定可以经过该点双连通分量中的每一个点。
用广义圆方树来维护一般无向图，每个方点的权值为其相邻的圆点的权值的最小值，然后可以用树剖来修改和查询。
但是这样修改的复杂度是不正确的，若一个圆点相邻有许多方点，像菊花图一样，那么复杂度是无法接受的。
考虑更改方点的权值定义，权值改为在圆方树上的其儿子权值的最小值。这样修改一个圆点时，只用考虑其父亲方点的权值的变化，这样修改复杂度就正确了。
在每个方点上用 (multiset) 来维护其儿子的权值，查询时两点的 (lca) 若为方点，则还要考虑其父亲圆点的贡献。
(code:)
#include<bits/stdc++.h>
#define maxn 400010
#define maxm 1600010
#define inf 2000000000
#define ls (cur<<1)
#define rs (cur<<1|1)
#define mid ((l+r)>>1)
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,q,tot,dfn_cnt,cnt,root=1;
int val[maxn],dfn[maxn],low[maxn],st[maxn];
int fa[maxn],de[maxn],siz[maxn],son[maxn],top[maxn],rev[maxn],mi[maxm];
vector<int> ve[maxn];
multiset<int> s[maxn];
char opt[5];
struct edge
{
int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
e[++edge_cnt]=(edge){to,head[from]};
head[from]=edge_cnt;
}
void addedge(int x,int y)
{
ve[x].push_back(y);
}
void tarjan(int x)
{
dfn[x]=low[x]=++dfn_cnt,st[++cnt]=x;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!dfn[y])
{
tarjan(y),low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y])
{
tot++;
int now;
do
{
now=st[cnt--];
addedge(tot,now),addedge(now,tot);
}while(now!=y);
addedge(tot,x),addedge(x,tot);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
void dfs_son(int x,int fath)
{
de[x]=de[fath]+1,siz[x]=1,fa[x]=fath,s[fath].insert(val[x]);
for(int i=0;i<ve[x].size();++i)
{
int y=ve[x][i];
if(y==fath) continue;
dfs_son(y,x),siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void dfs_chain(int x,int tp)
{
dfn[x]=++dfn_cnt,rev[dfn_cnt]=x,top[x]=tp;
if(son[x]) dfs_chain(son[x],tp);
for(int i=0;i<ve[x].size();++i)
{
int y=ve[x][i];
if(dfn[y]) continue;
dfs_chain(y,y);
}
}
void build(int l,int r,int cur)
{
if(l==r)
{
int x=rev[l];
if(x<=n) mi[cur]=val[x];
else mi[cur]=*s[x].begin();
return;
}
build(l,mid,ls),build(mid+1,r,rs);
mi[cur]=min(mi[ls],mi[rs]);
}
void modify(int l,int r,int pos,int v,int cur)
{
if(l==r)
{
mi[cur]=v;
return;
}
if(pos<=mid) modify(l,mid,pos,v,ls);
else modify(mid+1,r,pos,v,rs);
mi[cur]=min(mi[ls],mi[rs]);
}
int query(int L,int R,int l,int r,int cur)
{
if(L<=l&&R>=r) return mi[cur];
int v=inf;
if(L<=mid) v=min(v,query(L,R,l,mid,ls));
if(R>mid) v=min(v,query(L,R,mid+1,r,rs));
return v;
}
int ask(int x,int y)
{
int v=inf;
while(top[x]!=top[y])
{
if(de[top[x]]<de[top[y]]) swap(x,y);
v=min(v,query(dfn[top[x]],dfn[x],1,tot,root));
x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
v=min(v,query(dfn[x],dfn[y],1,tot,root));
if(x>n) v=min(v,val[fa[x]]);
return v;
}
int main()
{
read(n),read(m),read(q),tot=n,val[0]=inf;
for(int i=1;i<=n;++i) read(val[i]);
for(int i=1;i<=m;++i)
{
int x,y;
read(x),read(y);
add(x,y),add(y,x);
}
tarjan(1),dfn_cnt=0,memset(dfn,0,sizeof(dfn));
dfs_son(1,0),dfs_chain(1,1),build(1,tot,root);
while(q--)
{
int x,y;
scanf("%s",opt),read(x),read(y);
if(opt[0]=='C')
{
s[fa[x]].erase(s[fa[x]].find(val[x]));
s[fa[x]].insert(y),val[x]=y;
modify(1,tot,dfn[x],y,root);
modify(1,tot,dfn[fa[x]],*s[fa[x]].begin(),root);
}
else printf("%d
",ask(x,y));
}
return 0;
}