P4902

#include<algorithm>
#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define repu(i,u) for(int i=(h[u]);i;i=(ne[i]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define xx return
const int N=1e5+10;

int n,q;
int h[N],e[N*2],ne[N*2],idx;
int d[N],fa[N],siz_t[N],son[N];
int top[N],id[N],wt[N],cnt;

void add_edge(int a,int b){e[++idx]=b,ne[idx]=h[a],h[a]=idx;}

#define ls (p<<1)
#define rs (p<<1|1)
struct Tree{
	int max_n,add;
	#define max_n(p) t[p].max_n
	#define add(p) t[p].add
}t[N*4];

void spread(int p)
{
	if(add(p)&&d[add(p)]>d[max_n(ls)])
	{
		max_n(ls)=add(p);
		if(d[add(ls)]<d[add(p)])add(ls)=add(p);
	}
	if(add(p)&&d[add(p)]>d[max_n(rs)])
	{
		max_n(rs)=add(p);
		if(d[add(rs)]<d[add(p)])add(rs)=add(p);
	}
	add(p)=0;
}

void build(int p,int l,int r)
{
	max_n(p)=1;
	if(l==r){	
		xx;
	}
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}

void change(int p,int l,int r,int L,int R,int k)
{
	if(L<=l&&r<=R){
		if(d[k]>d[max_n(p)])
		{
			max_n(p)=k;
			if(d[k]>d[add(p)])add(p)=k;
		}
		xx;
	}
	spread(p);
	int mid=l+r>>1;
	if(L<=mid&&d[k]>d[max_n(ls)])change(ls,l,mid,L,R,k);
	if(R>mid&&d[k]>d[max_n(rs)])change(rs,mid+1,r,L,R,k);
	max_n(p)=(d[max_n(ls)]>d[max_n(rs)])?max_n(ls):max_n(rs);
}

int ask(int p,int l,int r,int x)
{
	if(l==r)xx max_n(p);
	spread(p);
	int mid=l+r>>1;
	if(x<=mid)xx ask(ls,l,mid,x);
	else xx ask(rs,mid+1,r,x);
}
#undef ls
#undef rs
#undef add
#undef max_n

void dfs1(int u,int fath)
{
	d[u]=d[fath]+1;
	fa[u]=fath;
	siz_t[u]=1;
	int max_son=-1;
	repu(i,u){
		int v=e[i];
		if(v==fath)continue;
		dfs1(v,u);
		siz_t[u]+=siz_t[v];
		if(siz_t[v]>max_son)son[u]=v,max_son=siz_t[v];
	}
}

void dfs2(int u,int topf)
{
	id[u]=++cnt;wt[cnt]=u;
	top[u]=topf;
	if(!son[u])xx;
	dfs2(son[u],topf);
	repu(i,u)
	{
		int v=e[i];
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}

void change_the_tree(int u)
{
	change(1,1,n,id[u],id[u]+siz_t[u]-1,u);
}

int ask_the_point(int u)
{
	xx ask(1,1,n,id[u]);
}

void solve()
{
	cin>>n>>q;
	rep(i,1,n-1){
		int u,v;cin>>u>>v;
		add_edge(u,v),add_edge(v,u);
	}
	dfs1(1,0),dfs2(1,1);
	change(1,1,n,id[1],id[1]+siz_t[1]-1,1);
	while(q--)
	{
		char opt;
		int u;cin>>opt>>u;
		if(opt=='C')change_the_tree(u);
		if(opt=='Q')cout<<ask_the_point(u)<<endl;
	}
	xx;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	xx 0;
}