/*
    题意：给定一个无向图，问有多少个三元组(x,y,z)，满足从x到z有一条简单路径经过y
    题解：双联通建立圆方树，任取两个圆点，答案就是两个圆点路径的点权和,方点点权为双连通分量大小，圆点点权为-1
    （-1是为了减去任取的两个圆点x,z,同时为了去掉割点的同时计算）
    利用双连通分量两个点之间的路径必然经过分量中的所有点
*/
#include <cstring>
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
typedef long long  ll;
const int MAXN = 1e5 + 20;
int n, m;
vector<int> pic[MAXN], tree[MAXN << 1];
stack<int> stk;
int dfn[MAXN],low[MAXN], max_dfn,size_cc,tot_cc;
int val[MAXN << 1];
ll ans;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}
void tarjan(int u)//构造圆方树
{
    low[u] = dfn[u] = ++max_dfn;
    stk.push(u);
    ++size_cc;
    for(auto v : pic[u])
    {
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] == dfn[u])
            {
                tot_cc++;//总的双联通分量数
                val[tot_cc + n] = 0; //方点
                while(!stk.empty())
                {
                    int x = stk.top();
                    stk.pop();
                    tree[tot_cc + n].push_back(x);
                    tree[x].push_back(tot_cc + n);
                    val[tot_cc + n]++;
                    if (x == v)
                        break;
                }
                tree[tot_cc + n].push_back(u);
                tree[u].push_back(tot_cc + n);
                val[tot_cc + n]++;
            }
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}
/*
        构造完圆方树后，问题转化为，统计树中任意两点路径的权值和，
    这个可以用换根dp来做，但是很麻烦。
        考虑每个点权的贡献，其对答案的贡献 = val*经过的路径条数
*/
int vztd[MAXN << 1], siz[MAXN << 1];
void dfs(int u,int fa)
{
    vztd[u] = 1;
    siz[u] = (u <= n);//统计圆点数量，编号小于n的一定是原点
    for(auto v : tree[u])
        if (v != fa)
        {
            dfs(v, u);
            ans += 2ll * val[u] * siz[u] * siz[v];
            // 子树各个点配对，包括了当前节点
            siz[u] += siz[v];
        }
    ans += 2ll * val[u] * siz[u] * (size_cc - siz[u]);
    //祖先节点和子节点配对，包含了祖先节点和当前节点的配对
}
int main()
{
    n = read();
    m = read();
    memset(val, -1, sizeof(val));
    for (int i = 1; i <= m;i++)
    {
        int x = read(), y = read();
        pic[x].push_back(y);
        pic[y].push_back(x);
    }
    for (int i = 1; i <= n;i++)
        if (!dfn[i])
        {
            while(!stk.empty())
                stk.pop();
            size_cc = 0;
            tarjan(i);
            dfs(i, 0);
        }
    cout << ans << endl;
    return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
 
const int MN = 100005;
const int MS = 524288;
const int Inf = 0x7fffffff;
 
int N, M, Q, cnt;
int w[MN * 2];
std::vector<int> G[MN], T[MN * 2];
std::multiset<int> S[MN * 2];
 
int dfn[MN * 2], low[MN], dfc;
int stk[MN], tp;
 
void Tarjan(int u) {
    low[u] = dfn[u] = ++dfc;
    stk[++tp] = u;
    for (auto v : G[u]) {
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = std::min(low[u], low[v]);
            if (low[v] == dfn[u]) {
                ++cnt;
                for (int x = 0; x != v; --tp) {
                    x = stk[tp];
                    T[cnt].push_back(x);
                    T[x].push_back(cnt);
                }
                T[cnt].push_back(u);
                T[u].push_back(cnt);
            }
        }
        else low[u] = std::min(low[u], dfn[v]);
    }
}
 
int idf[MN * 2], faz[MN * 2], siz[MN * 2], dep[MN * 2], son[MN * 2], top[MN * 2];
 
void DFS0(int u, int fz) {
    faz[u] = fz, dep[u] = dep[fz] + 1, siz[u] = 1;
    for (auto v : T[u]) if (v != fz) {
        DFS0(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}
 
void DFS1(int u, int fz, int tp) {
    dfn[u] = ++dfc, idf[dfc] = u, top[u] = tp;
    if (son[u]) DFS1(son[u], u, tp);
    for (auto v : T[u])
        if (v != fz && v != son[u])
            DFS1(v, u, v);
}
 
#define li (i << 1)
#define ri (i << 1 | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
 
int dat[MS];
 
void Build(int i, int l, int r) {
    if (l == r) { dat[i] = w[idf[l]]; return ; }
    Build(ls), Build(rs);
    dat[i] = std::min(dat[li], dat[ri]);
}
 
void Mdf(int i, int l, int r, int p, int x) {
    if (l == r) { dat[i] = x; return ; }
    if (p <= mid) Mdf(ls, p, x);
    else Mdf(rs, p, x);
    dat[i] = std::min(dat[li], dat[ri]);
}
 
int Qur(int i, int l, int r, int a, int b) {
    if (r < a || b < l) return Inf;
    if (a <= l && r <= b) return dat[i];
    return std::min(Qur(ls, a, b), Qur(rs, a, b));
}
 
int main() {
    scanf("%d%d%d", &N, &M, &Q);
    for (int i = 1; i <= N; ++i)
        scanf("%d", &w[i]);
    cnt = N;
    for (int i = 1; i <= M; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    Tarjan(1), DFS0(1, 0), dfc = 0, DFS1(1, 0, 1);
    for (int i = 1; i <= N; ++i) if (faz[i])
        S[faz[i]].insert(w[i]);
    for (int i = N + 1; i <= cnt; ++i)
        w[i] = *S[i].begin();
    Build(1, 1, cnt);
    for (int q = 1; q <= Q; ++q) {
        char opt[3]; int x, y;
        scanf("%s%d%d", opt, &x, &y);
        if (*opt == 'C') {
            Mdf(1, 1, cnt, dfn[x], y);
            if (faz[x]) {
                int u = faz[x];
                S[u].erase(S[u].lower_bound(w[x]));
                S[u].insert(y);
                if (w[u] != *S[u].begin()) {
                    w[u] = *S[u].begin();
                    Mdf(1, 1, cnt, dfn[u], w[u]);
                }
            }
            w[x] = y;
        }
        else {
            int Ans = Inf;
            while (top[x] != top[y]) {
                if (dep[top[x]] < dep[top[y]])
                    std::swap(x, y);
                Ans = std::min(Ans, Qur(1, 1, cnt, dfn[top[x]], dfn[x]));
                x = faz[top[x]];
            }
            if (dfn[x] > dfn[y]) std::swap(x, y);
            Ans = std::min(Ans, Qur(1, 1, cnt, dfn[x], dfn[y]));
            if (x > N) Ans = std::min(Ans, w[faz[x]]);
            printf("%d\n", Ans);
        }
    }
    return 0;
}