#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>using namespace std;typedef long long LL;const int maxn = 22222;struct Node{    int next; int to;}e[maxn * 2];int edge[maxn][10];#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1int len; int z;int size[maxn]; int son[maxn]; int deep[maxn], father[maxn];int color[maxn << 2];int sum[maxn << 2];int head[maxn];int pos[maxn]; int top[maxn];const int INF = 1 << 30;int sum1[maxn << 2];void add(int from, int to){    e[len].to = to;    e[len].next = head[from];    head[from] = len++;}void init(int x){    size[x] = 1; son[x] = 0;    for (int i = head[x]; i != -1; i = e[i].next){        int cc = e[i].to;        if (cc == father[x]) continue;        father[cc] = x; deep[cc] = deep[x] + 1;        init(cc);        size[x] += size[cc];        if (size[son[x]] < size[cc]) son[x] = cc;    }}void dfs(int x, int tp){    pos[x] = ++z; top[x] = tp;    if (son[x]) dfs(son[x], tp);    for (int i = head[x]; i != -1; i = e[i].next){        int cc = e[i].to;        if (cc == father[x] || cc == son[x]) continue;        dfs(cc, cc);    }}void build(int l, int r, int rt){    sum[rt] = -INF; sum1[rt] = INF;    color[rt] = 0;    if (l == r) return;    int mid = (l + r) >> 1;    build(lson); build(rson);}void down(int rt){    if (color[rt]){        sum[rt << 1] = -sum[rt << 1]; sum[rt << 1 | 1] = -sum[rt << 1 | 1]; sum1[rt << 1] = -sum1[rt << 1]; sum1[rt << 1 | 1] = -sum1[rt << 1 | 1];        swap(sum[rt << 1], sum1[rt << 1]); swap(sum[rt << 1 | 1], sum1[rt << 1 | 1]);        color[rt << 1] ^= 1; color[rt << 1 | 1] ^= 1;        color[rt] = 0;    }}void up(int rt){    sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);    sum1[rt] = min(sum1[rt << 1], sum1[rt << 1 | 1]);}void update(int L, int R, int l, int r, int rt){    if (L <= l&&r <= R) {        color[rt] ^= 1; sum[rt] = -sum[rt]; sum1[rt] = -sum1[rt]; swap(sum[rt], sum1[rt]);        return;    }    int mid = (l + r) >> 1;    down(rt);    if (L <= mid) update(L, R, lson);    if (R > mid) update(L, R, rson);    up(rt);}void update1(int key, int ans, int l, int r, int rt){    if (l == r){        sum1[rt] = ans;        sum[rt] = ans; return;    }    down(rt);    int mid = (l + r) >> 1;    if (key <= mid) update1(key, ans, lson);    else update1(key, ans, rson);    up(rt);}int ask(int L, int R, int l, int r, int rt){    if (L <= l&&r <= R) return sum[rt];    down(rt);    int mid = (l + r) >> 1;    int Max = -INF;    if (L <= mid) Max = max(Max, ask(L, R, lson));    if (R > mid) Max = max(Max, ask(L, R, rson));    return Max;}int gao(int x, int y){    int Max = -INF;    int fx = top[x]; int fy = top[y];    while (fx != fy){        if (deep[fx] < deep[fy]){            swap(x, y); swap(fx, fy);        }        Max = max(Max, ask(pos[fx], pos[x], 1, z, 1));        x = father[fx]; fx = top[x];    }    if (x == y) return Max;    if (deep[x]>deep[y])swap(x, y);    Max = max(Max, ask(pos[son[x]], pos[y], 1, z, 1));    return Max;}void gao1(int x, int y){    int fx = top[x]; int fy = top[y];    while (fx != fy){        if (deep[fx]<deep[fy]) swap(x, y), swap(fx, fy);        update(pos[fx], pos[x], 1, z, 1);        x = father[fx];  fx = top[x];    }    if (x == y) return;    if (deep[x]>deep[y]) swap(x, y);    update(pos[son[x]], pos[y], 1, z, 1);}int main(){    // freopen("input.txt","r",stdin);    //freopen("output.txt","w",stdout);    int t;    scanf("%d", &t);    int n, a, b;    char str[1000];    while (t--){        scanf("%d", &n);        len = 0; z = 0;        memset(head, -1, sizeof(head));        deep[1] = 1;        for (int i = 1; i < n; i++){            scanf("%d%d%d", &edge[i][0], &edge[i][1], &edge[i][2]);            add(edge[i][0], edge[i][1]);            add(edge[i][1], edge[i][0]);        }        init(1); dfs(1, 1); build(1, z, 1);        for (int i = 1; i < n; i++){            int a = edge[i][0]; int b = edge[i][1]; int c = edge[i][2];            if (deep[a]>deep[b]) swap(edge[i][0], edge[i][1]);            update1(pos[edge[i][1]], c, 1, z, 1);        }        while (scanf("%s", str) != EOF){            if (str[0] == ‘D‘) break;            if (str[0] == ‘Q‘){                scanf("%d%d", &a, &b);                int t = gao(a, b);                printf("%d\n", t);            }            if (str[0] == ‘C‘){                scanf("%d%d", &a, &b);                edge[a][2] = b;                update1(pos[edge[a][1]], b, 1, z, 1);            }            if (str[0] == ‘N‘){                scanf("%d%d", &a, &b);                gao1(a, b);            }        }    }    return 0;}