You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

CHANGE i v	Change the weight of the ith edge to v
NEGATE a b	Negate the weight of every edge on the path from a to b
QUERY a b	Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Sample Output

1
3

#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<string>
using namespace std;
const int maxn=10005;
const int inf=0x3f3f3f3f;
struct point
{
    int lazy,ll,rr,maxw,minw;
} tree[maxn*4];//线段树
int LL,RR,val,ind;
int pre[maxn],siz[maxn],dep[maxn],son[maxn];//第一次dfs处理的内容
int top[maxn],in[maxn],befcod[maxn];//第二次dfs处理的内容
int befval[maxn],dfstime;
vector<int> vec[maxn];//存边
struct edge1
{
    friend bool operator < (edge1 a1 ,edge1 a2); //由于要放入map容器，建立点与边的映射关系，所以得定义一个排序规则
    edge1(){a=b=0;}
    edge1(int x,int y){a=x,b=y;}
    int a,b;
};
bool operator < (edge1 a1 ,edge1 a2){//得对edge1的两个变量都排序，否则储存时会出问题，这与map的内部原理有关
    if(a1.a==a2.a)
        return a1.b<a2.b;
    return a1.a < a2.a;
}
struct edge2
{
    edge2(){w=cod=0;}
    edge2(int x,int y){w=x,cod=y;}
    int w,cod;
};
int edgecod[maxn];//用于储存边与点的对应关系
map<edge1,edge2> map1;
void dfs1(int u,int bef,int deep)
{
    pre[u]=bef;
    dep[u]=deep;
    siz[u]=1;//初始化u自身为一个节点
    for(int i=0; i<vec[u].size(); i++)
    {
        if(vec[u][i]==bef)
            continue;
        dfs1(vec[u][i],u,deep+1);
        siz[u]+=siz[vec[u][i]];//儿子节点的siz已经算出来了，用来更新u的siz
        if(siz[vec[u][i]]>siz[son[u]])
            son[u]=vec[u][i];//重儿子是siz值最大的儿子节点
    }
}
void dfs2(int u,int bef,int t)
{
    in[u]=++dfstime;
    befcod[dfstime]=u;
    top[u]=t;
    if(!son[u])//当为叶子节点时
        return;
    dfs2(son[u],u,t);//先处理重儿子，使得重链dfs序连续
    for(int i=0; i<vec[u].size(); i++)
    {
        if(vec[u][i]==bef||vec[u][i]==son[u])
            continue;
        dfs2(vec[u][i],u,vec[u][i]);//轻儿子的顶端节点就是自己
    }
}
void pushdown(int k)
{
    tree[k*2].lazy^=1;//两次取反则值不变
    tree[k*2+1].lazy^=1;
    int bet;
    bet=tree[k*2].maxw;
    tree[k*2].maxw=-tree[k*2].minw;
    tree[k*2].minw=-bet;
    bet=tree[k*2+1].maxw;
    tree[k*2+1].maxw=-tree[k*2+1].minw;
    tree[k*2+1].minw=-bet;
    tree[k].lazy=0;
}
void pushup(int k)
{
    tree[k].maxw=max(tree[k*2].maxw,tree[k*2+1].maxw);
    tree[k].minw=min(tree[k*2].minw,tree[k*2+1].minw);
}
void build(int k,int LL,int RR)
{
    tree[k].ll=LL,tree[k].rr=RR;
    tree[k].lazy=0;
    if(tree[k].ll==tree[k].rr)
    {
        int u=befcod[++ind];//由于线段树的性质，叶子节点出现的顺序是dfs序
        edge1 ed1(u,pre[u]);
        edge2 ed2=map1[ed1];
        tree[k].maxw=tree[k].minw=ed2.w;
        edgecod[ed2.cod]=u;
        return;
    }
    int bet=(tree[k].ll+tree[k].rr)/2;
    build(k*2,LL,bet);
    build(k*2+1,bet+1,RR);
    pushup(k);
}
void NEGATE(int k)//区间更新
{
    if(LL<=tree[k].ll&&RR>=tree[k].rr)
    {
        int bet=tree[k].maxw;
        tree[k].maxw=-tree[k].minw;
        tree[k].minw=-bet;
        tree[k].lazy^=1;
        return;
    }
    if(tree[k].lazy)
        pushdown(k);
    int bet=(tree[k].ll+tree[k].rr)/2;
    if(LL<=bet)
        NEGATE(k*2);
    if(RR>bet)
        NEGATE(k*2+1);
    pushup(k);
}
void CHANGE(int k,int point)//单点更新
{
    if(tree[k].ll==tree[k].rr){
        tree[k].minw=tree[k].maxw=val;
        return;
    }
    if(tree[k].lazy) pushdown(k);
    int bet=(tree[k].ll+tree[k].rr)/2;
    if(point<=bet) CHANGE(k*2,point);
    else CHANGE(k*2+1,point);
    pushup(k);
}
int QUERY(int k)//区间询查
{
    if(LL<=tree[k].ll&&RR>=tree[k].rr)
        return tree[k].maxw;
    if(tree[k].lazy)
        pushdown(k);
    int bet=(tree[k].ll+tree[k].rr)/2,askval=-inf;
    if(LL<=bet)
        askval=max(askval,QUERY(k*2));
    if(RR>bet)
        askval=max(askval,QUERY(k*2+1));
    return askval;
}
int ask(int x,int y)
{
    int ans=-inf,fx=top[x],fy=top[y];
    while(fx!=fy)//当x y不在同一条重链时
    {
        if(dep[fx]>=dep[fy])//先走较深的节点
        {
            LL=in[fx],RR=in[x];
            ans=max(ans,QUERY(1));
            x=pre[fx],fx=top[x];
        }
        else
        {
            LL=in[fy],RR=in[y];
            ans=max(ans,QUERY(1));
            y=pre[fy],fy=top[y];
        }
    }//循环，直到x y在同一重链上
    if(in[x]+1<=in[y]){
        LL=in[x]+1,RR=in[y];
        ans=max(ans,QUERY(1));
    }
    else if(in[y]+1<=in[x]){
        LL=in[y]+1,RR=in[x];
        ans=max(ans,QUERY(1));
    }
    return ans;
}
void change(int x,int y)//同理
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]>=dep[fy])
        {
            LL=in[fx],RR=in[x];
            NEGATE(1);
            x=pre[fx],fx=top[x];
        }
        else
        {
            LL=in[fy],RR=in[y];
            NEGATE(1);
            y=pre[fy],fy=top[y];
        }
    }
    if(in[x]+1<=in[y]){
        LL=in[x]+1,RR=in[y];
        NEGATE(1);
    }
    else if(in[y]+1<=in[x]){
        LL=in[y]+1,RR=in[x];
        NEGATE(1);
    }
}
char ss[10];
//int checkind;
//void check(int k) //输出叶子节点的值，用于检测树是否出现问题
//{
//    if(tree[k].ll==tree[k].rr){
//        printf("i==%d  maxw=%d minw=%d\n",++checkind,tree[k].maxw,tree[k].minw);
//        return;
//    }
//    if(tree[k].lazy) pushdown(k);
//    check(k*2);
//    check(k*2+1);
//}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out2.txt","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--){
        ind=dfstime=0;
        memset(son,0,sizeof(son));
        map1.clear();
        int n;
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            int x,y,w;
            scanf("%d %d %d",&x,&y,&w);
            vec[x].push_back(y);//存边
            vec[y].push_back(x);
            edge1 ed1(x,y);
            edge2 ed2(w,i);
            map1[ed1]=ed2;//建立点与边的映射
            ed1.a=y,ed1.b=x;
            map1[ed1]=ed2;
        }
        dfs1(1,0,1);
        dfs2(1,0,1);
        build(1,1,n);
        while(scanf("%s",ss)!=-1){
            if(ss[0]=='C'){
                int i;
                scanf("%d %d",&i,&val);
                CHANGE(1,in[edgecod[i]]);
            }
            else if(ss[0]=='N'){
                int a,b;
                scanf("%d %d",&a,&b);
                change(a,b);
            }
            else if(ss[0]=='Q'){
                int a,b;
                scanf("%d %d",&a,&b);
                printf("%d\n",ask(a,b));
            }
            else
                break;
//            checkind=0;
//            check(1);
//            printf("\n\n");
        }
        for(int i=1; i<=n; i++)
            vec[i].clear();
    }
    return 0;
}