口袋妖怪(又名神奇宝贝或宠物小精灵)红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前，冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后，到下一个冰地的楼梯才会被打开。

三个冰地分别如下：

当走出第三个冰地之后，就可以与馆主进行道馆战了。

馆主发现这个难度太小，导致经常有挑战者能通过，为了加大难度，将道馆分成了n个房间，每个房间中是两个冰块或障碍，表示一列冰地。任意两个房间之间均有且仅有一条路径相连，即这n个房间构成一个树状结构。

每个房间分成了A和B两个区域，每一区域都是一个薄冰块或者障碍物。每次只能移动到相邻房间的同一类区域(即若你现在在这个房间的A区域，那么你只能移动到相邻房间的A区域)或这个房间的另一区域。

现在挑战者从房间u出发，馆主在房间v，那么挑战者只能朝接近馆主所在房间的方向过去。一开始挑战者可以在房间u的任意一个冰块区域内。如果挑战者踩过的冰块数达到了最大值(即没有一种方案踩过的冰块数更多了)，那么当挑战者走到最后一个冰块上时，他会被瞬间传送到馆主面前与馆主进行道馆战。

自从馆主修改规则后已经经过了m天，每天要么是有一个挑战者来进行挑战，要么就是馆主将某个房间进行了修改。对于每个来的挑战者，你需要计算出他若要和馆主进行战斗需要经过的冰块数。

/*Author:wuhuajun*/#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#define lson l, mid, rt << 1#define rson mid+1, r, rt << 1 | 1using namespace std; typedef long long ll;typedef double dd;const int maxn=100010, INF = 1000000007; int edge, n, fa[maxn], sz[maxn], son[maxn], dep[maxn], hash[maxn], top[maxn];int h[maxn], num, a[maxn], x, y, tx, ty, Q, b[maxn];char s[22], s1[22], s2[22]; struct Edge{    int to, ne;} e[maxn * 2]; struct Seg{    int x[2][2], l[2], r[2];    void clear()    {        x[0][0] = x[0][1] = x[1][0] = x[1][1] = 0;        l[0] = l[1] = r[0] = r[1] = 0;    }} seg[maxn << 2], ans, c, L, R, ret; void close(){    exit(0);} void addedge(int x,int y){    e[edge].to = y;    e[edge].ne = h[x];    h[x] = edge++;} void dfs(int k,int from){    sz[k] = 1;    son[k] = 0;    dep[k] = dep[from] + 1;    for (int p=h[k];p!=-1;p=e[p].ne)    {        int to = e[p].to;        if (from == to) continue;        fa[to] = k;        dfs(to, k);        sz[k] += sz[to];        if (sz[to] > sz[son[k]]) son[k] = to;    }} void build(int k,int from){    hash[k] = ++num;    top[k] = from;    if (son[k]) build(son[k], from);    for (int p=h[k];p!=-1;p=e[p].ne)    {        int to = e[p].to;        if (to != fa[k] && to != son[k])            build(to, to);    }} //{{{Segment部分 int cal(int x,int y){    return max(-INF, max(x, y));} Seg operator + (Seg a,Seg b){    if (a.x[0][0] == 0 && a.x[0][1] == 0 && a.x[1][0] == 0 && a.x[1][1] == 0 && a.l[0] == 0 && a.l[1] == 0 && a.r[0] == 0 && a.r[1] == 0)        return b;    if (b.x[0][0] == 0 && b.x[0][1] == 0 && b.x[1][0] == 0 && b.x[1][1] == 0 && b.l[0] == 0 && b.l[1] == 0 && b.r[0] == 0 && b.r[1] == 0)        return a;    c.x[0][0] = cal(a.x[0][0] + b.x[0][0], a.x[0][1] + b.x[1][0]);    c.x[0][1] = cal(a.x[0][0] + b.x[0][1], a.x[0][1] + b.x[1][1]);    c.x[1][0] = cal(a.x[1][0] + b.x[0][0], a.x[1][1] + b.x[1][0]);    c.x[1][1] = cal(a.x[1][0] + b.x[0][1], a.x[1][1] + b.x[1][1]);    c.l[0] = max(a.l[0], max(a.x[0][0] + b.l[0], a.x[0][1] + b.l[1]));    c.l[1] = max(a.l[1], max(a.x[1][0] + b.l[0], a.x[1][1] + b.l[1]));    c.r[0] = max(b.r[0], max(b.x[0][0] + a.r[0], b.x[1][0] + a.r[1]));    c.r[1] = max(b.r[1], max(b.x[0][1] + a.r[0], b.x[1][1] + a.r[1]));    return c;} void change(int L,int R,int val1,int val2,int l,int r,int rt){    if (L <= l && r <= R)    {        seg[rt].x[0][0] = seg[rt].l[0] = seg[rt].r[0] = val1;        seg[rt].x[1][1] = seg[rt].l[1] = seg[rt].r[1] = val2;        if (val1 == 1 && val2 == 1)        {            seg[rt].l[0] = seg[rt].l[1] = seg[rt].r[0] = seg[rt].r[1] = 2;            seg[rt].x[0][1] = seg[rt].x[1][0] = 2;        }        else        {            seg[rt].x[0][1] = seg[rt].x[1][0] = -INF;        }        seg[rt].l[0] = max(seg[rt].l[0], 0);        seg[rt].l[1] = max(seg[rt].l[1], 0);        seg[rt].r[0] = max(seg[rt].r[0], 0);        seg[rt].r[1] = max(seg[rt].r[1], 0);        return;    }    int mid = (l + r) >> 1;    if (L <= mid)        change(L,R,val1,val2,lson);    if (mid + 1 <= R)        change(L,R,val1,val2,rson);    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];} Seg query(int L,int R,int l,int r,int rt){    if (L <= l && r <= R)    {        return seg[rt];    }    int mid = (l + r) >> 1;    Seg ans;    ans.clear();    if (L <= mid)        ans = ans + query(L,R,lson);    if (mid + 1 <= R)        ans = ans + query(L,R,rson);    return ans;}//}}} Seg get_ans(){    tx = top[x];    ty = top[y];    L.clear();    R.clear();    while (tx != ty)    {        if (dep[tx] < dep[ty])        {            R = query(hash[ty], hash[y], 1, n, 1) + R;            y = fa[ty];            ty = top[y];        }        else        {            L = query(hash[tx], hash[x], 1, n, 1) + L;            x = fa[tx];            tx = top[x];        }    }    if (dep[x] < dep[y])    {        R = query(hash[x], hash[y], 1, n, 1) + R;    }    else    {        L = query(hash[y], hash[x], 1, n, 1) + L;    }    swap(L.x[0][1], L.x[1][0]);    swap(L.l[0], L.r[0]);    swap(L.l[1], L.r[1]);    return L + R;} void init(){    scanf("%d %d",&n,&Q);    memset(h,-1,sizeof(h));    for (int i=1;i<=n-1;i++)    {        scanf("%d %d",&x, &y);        addedge(x, y);        addedge(y, x);    }    for (int i=1;i<=n;i++)    {        scanf("%s", s1);        a[i] = s1[0] == ‘.‘ ? 1 : -INF;        b[i] = s1[1] == ‘.‘ ? 1 : -INF;    }    dfs(1, 0);    build(1, 1);    /*    for (int i=1;i<=n;i++)    {        printf("i:%d top:%d hash:%d\n",i, top[i], hash[i]);    }    */    for (int i=1;i<=n;i++)        change(hash[i], hash[i], a[i], b[i], 1, n, 1);    while (Q--)    {        scanf("%s", s);        if (s[0] == ‘Q‘)        {            scanf("%d %d",&x, &y);            ret = get_ans();            printf("%d\n", max(ret.l[0], ret.l[1]));        }        else        {            scanf("%d",&x);            scanf("%s", s1);            int t1 = s1[0] == ‘.‘ ? 1 : -INF;            int t2 = s1[1] == ‘.‘ ? 1 : -INF;            change(hash[x], hash[x], t1, t2, 1, n, 1);        }    }} int main (){    init();    close();    return 0;}