RT

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=5e4+1;
const int mod=1e9+7;
string s[maxn];
int read(){
	char op = getchar(); int x = 0, f = 1;
	while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();}
	while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar();
	return x * f;
}
void write(int x){
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
int n,m;
struct ed{
	int h,t;
}e[maxn<<1];
int last[maxn],ecnt=0; 
void link(int x,int y){
	e[++ecnt].h=last[x];
	e[ecnt].t=y;
	last[x]=ecnt;
}
int rnk[maxn],dfn[maxn],top[maxn],fa[maxn],siz[maxn],dep[maxn],son[maxn],dcnt=0;
void dfs1(int u,int f){
	fa[u]=f;
	siz[u]=1;
	dep[u]=dep[f]+1;
	for(int i=last[u];i;i=e[i].h){
		int v=e[i].t;
		if(v==f)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])son[u]=v;
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	dfn[u]=++dcnt;
	rnk[dcnt]=u;
	if(son[u]){
		dfs2(son[u],tp);
		for(int i=last[u];i;i=e[i].h){
			int v=e[i].t;
			if(v==fa[u]||son[u]==v)continue;
			dfs2(v,v);
		}
	}
}
struct pos{
	int lmax[2],rmax[2],dismax[2][2];
	pos(){memset(lmax,0,sizeof lmax);memset(rmax,0,sizeof rmax);memset(dismax,0,sizeof dismax);} 
}p[maxn<<2];
void push_up(pos& a,pos b,pos c){
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){
			a.lmax[i]=max(a.lmax[i],max(b.lmax[i],b.dismax[i][j]+c.lmax[j]));
		}
	}
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){
			a.rmax[i]=max(a.rmax[i],max(c.rmax[i],c.dismax[j][i]+b.rmax[j]));
		}
	}
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){
			a.dismax[i][j]=-114514;
			for(int k=0;k<=1;k++){
				a.dismax[i][j]=max(a.dismax[i][j],b.dismax[i][k]+c.dismax[k][j]);
			}
		}
	}
}

void New(pos& a,int l){
	int c[2];
	c[0]=(s[l][0]=='.');
	c[1]=(s[l][1]=='.');
	if(c[0]&&c[1]){
		for(int i=0;i<=1;i++){
			a.lmax[i]=a.rmax[i]=2;
		}
		for(int i=0;i<=1;i++){
			for(int j=0;j<=1;j++){
				a.dismax[i][j]=(i==j)?1:2;
			}
		}
		return ;
	}
	if(c[0]||c[1]){
		int op=!c[0];
		a.lmax[op]=a.rmax[op]=a.dismax[op][op]=1;
		a.lmax[!op]=a.rmax[!op]=0;
		a.dismax[!op][op]=a.dismax[op][!op]=a.dismax[!op][!op]=-114514;
		return ;
	}
	for(int i=0;i<=1;i++){
		a.lmax[i]=a.rmax[i]=0;
	}
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){
			a.dismax[i][j]=-114514;
		}
	}
}
#define ls(x) x<<1
#define rs(x) x<<1|1
void build(int x,int l,int r){
	if(l==r){
		New(p[x],rnk[l]);
		return ;
	}
	int mid=l+r>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	push_up(p[x],p[ls(x)],p[rs(x)]);
}
void update(int x,int l,int r,int nx){
//	cout<<x;
	if(l>nx||r<nx)return ;
	if(l==nx&&r==nx){
		New(p[x],rnk[nx]);
		return ;
	}
	int mid=l+r>>1;
	update(ls(x),l,mid,nx);
	update(rs(x),mid+1,r,nx);
	push_up(p[x],p[ls(x)],p[rs(x)]);
}
pos query(int x,int l,int r,int nl,int nr){
//	cout<<x<<endl;
	if(l>=nl&&r<=nr)return p[x];
	int mid=l+r>>1;
	
	if(nr<=mid)return query(ls(x),l,mid,nl,nr);
	else if(nl>mid) return query(rs(x),mid+1,r,nl,nr);
	else {
		pos t;
		push_up(t,query(ls(x),l,mid,nl,nr),query(rs(x),mid+1,r,nl,nr));
		return t;
	}
}
void rev(pos& a){
	for(int i=0;i<=1;i++){
		swap(a.lmax[i],a.rmax[i]);
	}
	swap(a.dismax[1][0],a.dismax[0][1]);
}
//void print(pos t)
//{
//	for (int i = 0; i < 2; i++)
//	{
//		cout << "lmax[" << i << "]=" << t.lmax[i] << endl;
//		cout << "rmax[" << i << "]=" << t.rmax[i] << endl;
//	}
//	for (int i = 0; i < 2; i++)
//		for (int j = 0; j < 2; j++)
//		{
//			cout << "dis[" << i << "][" << j << "]=" << t.dismax[i][j] << endl;
//		}
//}
int len(int x,int y){
	pos ret,ret1,ret2;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]){
//			cout<<top[y]<<' '<<y<<endl;
//			cout << dfn[top[x]] << "#" << dfn[x] << endl;
//			print(query(1,1,n,dfn[top[x]],dfn[x]));
			push_up(ret1,query(1,1,n,dfn[top[x]],dfn[x]),ret1);
			x=fa[top[x]];
		}else{
//			cout<<top[x]<<' '<<x<<endl;
//			cout << dfn[top[y]] << "@" << dfn[y] << endl;
//			print(query(1,1,n,dfn[top[y]],dfn[y]));
			push_up(ret2,query(1,1,n,dfn[top[y]],dfn[y]),ret2);
			y=fa[top[y]];
		}
	}
	if(dep[x]>dep[y])
	{
//		cout << dfn[y] << "#" << dfn[x] << endl;
//		print(query(1,1,n,dfn[y],dfn[x]));
		push_up(ret1,query(1,1,n,dfn[y],dfn[x]),ret1);
	}
	else
	{
//		cout << dfn[x] << "@" << dfn[y] << endl;
//		print(query(1,1,n,dfn[x],dfn[y]));
		push_up(ret2,query(1,1,n,dfn[x],dfn[y]),ret2);
	}
	rev(ret1);
	push_up(ret,ret1,ret2);
	return max(ret.lmax[0],ret.lmax[1]);
}
void cinn(){
	n=read(),m=read();
	for(int i=1,x,y;i<n;i++){
		x=read(),y=read();
		link(x,y);
		link(y,x);
	}
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
}
signed main(){
	cinn();
	dfs1(1,0);
//	cout<<1;
	dfs2(1,1);
//	cout<<2;
//	for(int i=1;i<=n;i++){
//		cout<<i<<" "<<dfn[i]<<" "<<top[i]<<endl;
//	}
//	cout<<endl;
	build(1,1,n);
	char opt;
	int a,b;
	while(m--){
		//while(opt!='C'&&opt!='Q')opt=getchar();
		cin>>opt;
//		cout << "opt = " << opt << '\n'; 
		if(opt=='C'){
			a=read();
			cin>>s[a];
			update(1,1,n,dfn[a]);
		}
		if(opt=='Q'){
			a=read();
			b=read();
			write(len(a,b));
			putchar('\n');
		}
	}
	return 0;
}
/*
5 11000
1 2
2 3
2 4
1 5
.#
..
#.
.#
..
C 1 ##
Q 3 4
Q 3 4
*/