#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

int n, q, u, v, head[MAXN], EdgeCnt;
char ch;

struct Edge {
	int v, pre;
} e[MAXN << 1];

void AddEdge(int u, int v) {
	EdgeCnt++;
	e[EdgeCnt].v = v;
	e[EdgeCnt].pre = head[u];
	head[u] = EdgeCnt;
}

int cnt, fa[MAXN], dep[MAXN], son[MAXN], siz[MAXN], top[MAXN], dfn[MAXN], rnk[MAXN];

void dfs1(int x) {
	son[x] = -1;
	siz[x] = 1;
	for(int i = head[x]; i; i = e[i].pre) {
		int to = e[i].v;
		if(!dep[to]) {
			dep[to] = dep[x] + 1;
			fa[to] = x;
			dfs1(to);
			siz[x] += siz[to];
			if(son[x] == -1 || siz[to] > siz[son[x]]) son[x] = to;
		}
	}
}

void dfs2(int x, int t) {
	top[x] = t;
	++cnt;
	dfn[x] = cnt;
	rnk[cnt] = x;
	if(son[x] == -1) return;
	dfs2(son[x], t);
	for(int i = head[x]; i; i = e[i].pre) {
		int to = e[i].v;
		if(to != son[x] && to != fa[x])
			dfs2(to, to);
	}
}

struct SegmentTree {
	int id[MAXN << 2];
	
	void push_up(int p) {
		id[p] = max(id[ls(p)], id[rs(p)]);
	}
	
	void build(int p, int l, int r) {
		if(l == r) {
			id[p] = 1;
			return;
		}
		int mid = (l + r) >> 1;
		build(ls(p), l, mid);
		build(rs(p), mid + 1, r);
		push_up(p);
	}
	
	void update(int p, int l, int r, int x) {
		if(l == r) {
			id[p] = x;
			return;
		}
		int mid = (l + r) >> 1;
		if(x <= mid) update(ls(p), l, mid, x);
		else update(rs(p), mid + 1, r, x);
		push_up(p);
	}
	
	int query(int p, int nl, int nr, int l, int r) {
		if(nl <= l && r <= nr) return id[p];
		int mid = (l + r) >> 1, ret = 1;
		if(nl <= mid) ret = max(ret, query(ls(p), nl, nr, l, mid));
		if(mid < nr) ret = max(ret, query(rs(p), nl, nr, mid + 1, r));
		return ret;
	}
} st;

int Query(int x, int y) {
	int fx = top[x], fy = top[y], ret = 1;
	while(fx != fy) {
		if(dep[fx] >= dep[fy])
			ret = max(ret, st.query(1, dfn[fx], dfn[x], 1, n)), x = fa[fx];
		else
			ret = max(ret, st.query(1, dfn[fy], dfn[y], 1, n)), y = fa[fy];
		fx = top[x];
		fy = top[y];
	}
	if(dfn[x] < dfn[y]) ret = max(ret, st.query(1, dfn[x], dfn[y], 1, n));
	else ret = max(ret, st.query(1, dfn[y], dfn[x], 1, n));
	return ret;
}

int main() {
	scanf("%d%d", &n, &q);
	for(int i = 1; i < n; ++i) {
		scanf("%d%d", &u, &v);
		AddEdge(u, v); AddEdge(v, u);
	}
	dep[1] = 1;
	dfs1(1); dfs2(1, 1);
	st.build(1, 1, n);
	while(q--) {
		cin >> ch;
		scanf("%d", &u);
		if(ch == 'C') st.update(1, 1, n, u);
		else printf("%d\n", rnk[Query(1, u)]);
	}
	return 0;
}

样例可以过，但只得了8分，这是为什么？