先建出来圆方树，圆点为本身的权值，方点为与之相连的圆点的最小值。

很明显答案就是询问的两点间的路径上的最小值。

考虑修改操作

\(1\) .圆点：直接改

\(2\) .方点：对每个方点开一个 \(multiset\) ，存储相邻的点的权值。

我们发现这样的话修改一个圆点的时候会修改很多方点，效率低。

我们将 \(multiset\) 改为存储儿子的权值，这样我们修改圆点的时候就只用修改相应的父亲节点了。

用树剖维护修改和查询操作就行了。注意查询时若 \(lca\) 是方点，还要考虑其父亲圆点。

注意 \(multiset\) 的删除操作的正确用法。

#include<iostream>
#include<cstdio>
#include<set>
#define lson (k<<1)
#define rson ((k<<1)|1)
using namespace std;
int n, m, q, tot, Tot, num, Top, x, y, cnt, a, b;
const int N = 400010;
int head[N], to[N], nt[N], Head[N], To[N], Nt[N], dfn[N], low[N], zhan[N], w[N], nfd[N], siz[N], son[N], top[N], dep[N], fa[N], tr[N << 2];
char opt[3];
multiset<int>s[N];
multiset<int>::iterator it;
void add(int f, int t)
{
	to[++tot] = t; nt[tot] = head[f]; head[f] = tot;
}
void ADD(int f, int t)
{
	To[++Tot] = t; Nt[Tot] = Head[f]; Head[f] = Tot;
}
void Tarjan(int x)
{
	dfn[x] = low[x] = ++cnt; zhan[++Top] = x;
	for (int i = Head[x]; i; i = Nt[i])
		if (!dfn[To[i]])
		{
			Tarjan(To[i]); low[x] = min(low[x], low[To[i]]);
			if (low[To[i]] >= dfn[x])
			{
				add(++num, x); add(x, num);
				int t;
				do
				{
					t = zhan[Top--]; add(num, t); add(t, num);
				} while (t != To[i]);
			}
		}
		else low[x] = min(low[x], dfn[To[i]]);
}
void dfs1(int x, int f)
{
	fa[x] = f; dep[x] = dep[f] + 1; siz[x] = 1;
	if (x <= n && f)s[f].insert(w[x]);
	for (int i = head[x]; i; i = nt[i])
		if (to[i] != f)
		{
			dfs1(to[i], x);
			siz[x] += siz[to[i]];
			if (siz[to[i]] > siz[son[x]])son[x] = to[i];
		}
	if (x > n)w[x] = *s[x].begin();
}
void dfs2(int x, int t)
{
	top[x] = t; dfn[x] = ++cnt; nfd[cnt] = x;
	if (son[x])dfs2(son[x], t);
	else return;
	for (int i = head[x]; i; i = nt[i])
		if (to[i] != fa[x] && to[i] != son[x])dfs2(to[i], to[i]);
}
void pushup(int k)
{
	tr[k] = min(tr[lson], tr[rson]);
}
void build(int k, int l, int r)
{
	if (l == r)
	{
		tr[k] = w[nfd[l]];
		return;
	}
	int mid = (l + r) >> 1;
	build(lson, l, mid); build(rson, mid + 1, r);
	pushup(k);
}
int ask(int k, int l, int r, int x, int y)
{
	if (x <= l && r <= y)return tr[k];
	int mid = (l + r) >> 1, res = 2e9;
	if (x <= mid)res = min(res, ask(lson, l, mid, x, y));
	if (mid + 1 <= y)res = min(res, ask(rson, mid + 1, r, x, y));
	return res;
}
void change(int k, int l, int r, int pos, int val)
{
	if (l == r)
	{
		tr[k] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid)change(lson, l, mid, pos, val);
	else change(rson, mid + 1, r, pos, val);
	pushup(k);
}
int cask(int x, int y)
{
	int res = 2e9;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]])swap(x, y);
		res = min(res, ask(1, 1, num, dfn[top[x]], dfn[x])); x = fa[top[x]];
	}
	if (dep[x] < dep[y])swap(x, y);
	res = min(res, ask(1, 1, num, dfn[y], dfn[x]));
	if (y > n)res = min(res, w[fa[y]]);
	return res;
}
int main()
{
	cin >> n >> m >> q; num = n;
	for (int i = 1; i <= n; ++i)scanf("%d", &w[i]); w[0] = 2e9;
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d", &x, &y);
		ADD(x, y); ADD(y, x);
	}
	Tarjan(1); cnt = 0; dfs1(1, 0); dfs2(1, 1); build(1, 1, num);
	while (q--)
	{
		scanf("%s%d%d", opt, &a, &b);
		if (opt[0] == 'C')
		{
			if (fa[a])
			{
				it = s[fa[a]].find(w[a]), s[fa[a]].erase(it), s[fa[a]].insert(b);
				w[fa[a]] = *s[fa[a]].begin(), change(1, 1, num, dfn[fa[a]], w[fa[a]]);
			}
			w[a] = b; change(1, 1, num, dfn[a], b);
		}
		else printf("%d\n", cask(a, b));
	}
	return 0;
}