#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 100'447;
const int LOG = 17;
VI g[N];
int color[N];
int col[N];
int pos[N];
int nxt[N];
int tin[N], tout[N];
int top[N];
int up[LOG][N];
int sz[N];
int p[N];
int h[N];
int ps = 0;
int t = 0;

void dfsSZ(int v, int par, int hei)
{
	h[v] = hei;
	sz[v] = 1;
	p[v] = par;
	for (auto& to : g[v])
	{
		if (to == par)
			continue;
		dfsSZ(to, v, hei + 1);
		sz[v] += sz[to];
		if (g[v][0] == par || sz[g[v][0]] < sz[to])
			swap(g[v][0], to);
	}
}

void dfsHLD(int v, int par, int tp)
{
	pos[v] = ps++;
	tin[v] = t++;
	top[v] = tp;
	FOR (i, 0, SZ(g[v]))
	{
		int to = g[v][i];
		if (to == par)
			continue;
		if (i == 0)
			dfsHLD(to, v, tp);
		else
			dfsHLD(to, v, to);
	}
	tout[v] = t - 1;
}

bool is_parent(int par, int v)
{
	return tin[par] <= tin[v] && tout[v] <= tout[par];
}
int lca(int u, int v)
{
	if (is_parent(u, v))
		return u;
	RFOR (i, LOG, 0)
	{
		int nu = up[i][u];
		if (!is_parent(nu, v))
			u = nu;
	}
	return up[0][u];
}

void f(const int cl, int st, int en, int& mn, int& cnt)
{
	FOR (i, st, en)
	{
		cnt++;
		if (col[i] == cl)
		{
			mn = min(mn, cnt);
			cnt = 0;
		}
	}
}

PII solve(int v, int lca, const int cl)
{
	int mn = N, cnt = N;
	int nv = nxt[v];
	//cerr << v << ' ' << nv << '\n';
	while (!is_parent(nv, lca))
	{
		f(cl, pos[v], pos[nv] + 1, mn, cnt);
		v = p[nv];
		nv = nxt[v];
	}
	f(cl, pos[v], pos[lca] + 1, mn, cnt);
	return {mn, cnt};
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, q;
	cin >> n >> q;
	FOR (i, 0, n)
		cin >> color[i];
	FOR (i, 0, n - 1)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].PB(v);
		g[v].PB(u);
	}
	dfsSZ(0, 0, 0);
	dfsHLD(0, -1, 0);
	FOR (i, 0, n) up[0][i] = p[i];
	FOR (i, 1, LOG)
	{
		FOR (v, 0, n)
			up[i][v] = up[i - 1][up[i - 1][v]];
	}
	FOR (i, 0, n)
		pos[i] = n - 1 - pos[i];
	FOR (i, 0, n)
		nxt[i] = top[i];
	FOR (i, 0, n)
		col[pos[i]] = color[i];
	//FOR (i, 0, n)
	//{
	//	cerr << i << ' ' << p[i] << ' ' << top[i] << ' ' << pos[i] << ' ' << col[i] << ' ' << nxt[i] << '\n';
	//}
	FOR (i, 0, q)
	{
		char ch;
		cin >> ch;
		if (ch == 'Q')
		{
			int u, v, cl;
			cin >> u >> v >> cl;
			u--, v--;
			int lc = lca(u, v);
			//cerr << u << ' ' << v << ' ' << lc << '\n';
			auto p1 = solve(u, lc, cl);
			auto p2 = solve(v, lc, cl);
			int ans = min(p1.F, p2.F);
			if (color[lc] != cl)
				ans = min(ans, p1.S + p2.S);
			if (ans == N)
				ans = -1;
			cout << ans << '\n';
		}
		else
		{
			int v, c;
			cin >> v >> c;
			v--;
			color[v] = c;
			col[pos[v]] = c;
		}
	}
	
	cerr << db(clock()) / CLOCKS_PER_SEC << '\n';
	return 0;
}