#include<cstdio>#include<iostream>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int n,m,cnt,tt,x0,y0,x1,y1;struct segtree{    int l,r;    int a_to_a,a_to_b,b_to_a,b_to_b;}tree[1000010];struct edge{    int to,next;}e[200010];int head[100010];segtree query;bool mrk[100010],mrkl[100010],mrkr[100010];int fa[100010][20],depth[100010],son[100010];int chain[100010],belong[100010],place[100010],pplace[100010];inline int max(int a,int b,int c,int d){	if (b>a)a=b;	if (c>a)a=c;	if (d>a)a=d;	return a;}inline void ins(int u,int v){    e[++cnt].to=v;    e[cnt].next=head[u];    head[u]=cnt;}inline void insert(int u,int v){    ins(u,v);    ins(v,u);}inline void dfs1(int x,int dep){    if (mrk[x])return;mrk[x]=1;    son[x]=1;depth[x]=dep;    for (int i=1;i<20;i++)      fa[x][i]=fa[fa[x][i-1]][i-1];    for (int i=head[x];i;i=e[i].next)      if (!mrk[e[i].to])      {        fa[e[i].to][0]=x;        dfs1(e[i].to,dep+1);        son[x]+=son[e[i].to];      }}inline void dfs2(int x,int chain){    place[x]=++tt;pplace[tt]=x;    belong[x]=chain;    int mx=-1,res=-1;    for (int i=head[x];i;i=e[i].next)      if (e[i].to!=fa[x][0])        {            if (son[e[i].to]>mx)            {                mx=son[e[i].to];                res=e[i].to;            }        }    if (res==-1)return;    dfs2(res,chain);    for (int i=head[x];i;i=e[i].next)      if (res!=e[i].to&&fa[x][0]!=e[i].to)      dfs2(e[i].to,e[i].to);}inline int LCA(int x,int y){    if (depth[x]<depth[y])swap(x,y);    int res=depth[x]-depth[y];    for (int i=0;i<20;i++)      if (res & (1<<i))x=fa[x][i];    for (int i=19;i>=0;i--)      if (fa[x][i]!=fa[y][i])        {            x=fa[x][i];            y=fa[y][i];        }    if (x==y)return x;    return fa[x][0];}segtree merge(segtree a,segtree b){    segtree k;    k.a_to_a=k.a_to_b=k.b_to_a=k.b_to_b=-1;    k.l=min(a.l,b.l); k.r=max(a.r,b.r);         if (a.a_to_a!=-1&&b.a_to_a!=-1)k.a_to_a=a.a_to_a+b.a_to_a+1;    if (a.a_to_b!=-1&&b.b_to_a!=-1)    {        if (k.a_to_a==-1)k.a_to_a=a.a_to_b+b.b_to_a+1;        else k.a_to_a=min(k.a_to_a,a.a_to_b+b.b_to_a+1);    }         if (a.a_to_a!=-1&&b.a_to_b!=-1)k.a_to_b=a.a_to_a+b.a_to_b+1;    if (a.a_to_b!=-1&&b.b_to_b!=-1)    {        if (k.a_to_b==-1)k.a_to_b=a.a_to_b+b.b_to_b+1;        else k.a_to_b=min(k.a_to_b,a.a_to_b+b.b_to_b+1);    }         if (a.b_to_a!=-1&&b.a_to_a!=-1)k.b_to_a=a.b_to_a+b.a_to_a+1;    if (a.b_to_b!=-1&&b.b_to_a!=-1)    {        if (k.b_to_a==-1)k.b_to_a=a.b_to_b+b.b_to_a+1;        else k.b_to_a=min(k.b_to_a,a.b_to_b+b.b_to_a+1);    }         if (a.b_to_a!=-1&&b.a_to_b!=-1)k.b_to_b=a.b_to_a+b.a_to_b+1;    if (a.b_to_b!=-1&&b.b_to_b!=-1)    {        if (k.b_to_b==-1)k.b_to_b=a.b_to_b+b.b_to_b+1;        else k.b_to_b=min(k.b_to_b,a.b_to_b+b.b_to_b+1);    }    return k;}inline void buildtree(int now,int l,int r){    tree[now].l=l;tree[now].r=r;    if (l==r)    {        tree[now].a_to_a=tree[now].a_to_b=tree[now].b_to_a=tree[now].b_to_b=-1;        if (mrkl[pplace[l]])tree[now].a_to_a=0;        if (mrkr[pplace[l]])tree[now].b_to_b=0;        if (mrkl[pplace[l]]&&mrkr[pplace[r]])        {            tree[now].a_to_b=1;            tree[now].b_to_a=1;        }        return;    }    int mid=(l+r)>>1;    buildtree(now<<1,l,mid);    buildtree(now<<1|1,mid+1,r);    tree[now]=merge(tree[now<<1],tree[now<<1|1]);}inline segtree ask_in_tree(int now,int x,int y){    int l=tree[now].l,r=tree[now].r;    if (l==x&&r==y)return tree[now];    int mid=(l+r)>>1;    if (y<=mid)return ask_in_tree(now<<1,x,y);    else if (x>mid)return ask_in_tree(now<<1|1,x,y);    else return merge(ask_in_tree(now<<1,x,mid),ask_in_tree(now<<1|1,mid+1,y));}inline segtree ask(int from,int to){    int l,r;    segtree s;s.l=s.r=0;    while (belong[from]!=belong[to])    {        l=place[belong[from]];        r=place[from];        if (!s.l)s=ask_in_tree(1,l,r);            else s=merge(s,ask_in_tree(1,l,r));        from=fa[belong[from]][0];    }    l=place[to];    r=place[from];    if (!s.l)s=ask_in_tree(1,l,r);        else s=merge(s,ask_in_tree(1,l,r));    return s;}inline void cal(){    int a=read(),b=read(),lca=LCA(a,b);    segtree q1=ask(a,lca);    segtree q2=ask(b,lca);    swap(q2.a_to_b,q2.b_to_a);    q1=merge(q1,q2);    int ans=max(q1.a_to_a,q1.a_to_b,q1.b_to_a,q1.b_to_b);    printf("%d\n",ans);}inline void change_in_tree(int now,int x,bool m1,bool m2){    int l=tree[now].l,r=tree[now].r;    if (l==r)    {        tree[now].a_to_a=tree[now].a_to_b=tree[now].b_to_a=tree[now].b_to_b=-1;        if (m1)tree[now].a_to_a=0;        if (m2)tree[now].b_to_b=0;        if (m1&&m2)tree[now].a_to_b=tree[now].b_to_a=1;        return;    }    int mid=(l+r)>>1;    if (x<=mid)change_in_tree(now<<1,x,m1,m2);    else change_in_tree(now<<1|1,x,m1,m2);    tree[now]=merge(tree[now<<1],tree[now<<1|1]);}inline void wrk(){    int a=read();    bool m1=0,m2=0;    char ch=getchar();while (ch!=‘.‘&&ch!=‘#‘)ch=getchar();    if (ch==‘.‘)m1=1;    ch=getchar();while (ch!=‘.‘&&ch!=‘#‘)ch=getchar();    if (ch==‘.‘)m2=1;    change_in_tree(1,belong[a],m1,m2);}int main(){    n=read();m=read();    for (int i=1;i<n;i++)    {        int x=read(),y=read();        insert(x,y);    }    for(int i=1;i<=n;i++)    {    	char ch=getchar();while (ch!=‘#‘&&ch!=‘.‘)ch=getchar();        if (ch==‘.‘)mrkl[i]=1;        ch=getchar();while (ch!=‘#‘&&ch!=‘.‘)ch=getchar();        if (ch==‘.‘)mrkr[i]=1;    }    dfs1(1,0);    dfs2(1,1);    buildtree(1,1,n);    for(int i=1;i<=m;i++)    {        char opr=getchar();        while (opr!=‘Q‘&&opr!=‘C‘)opr=getchar();        if (opr==‘Q‘)cal();        if (opr==‘C‘)wrk();    }    return 0;}