#include<iostream>
#include<algorithm>
using namespace std;

#define maxn 100010
#define inf 0x3f3f3f3f

int k = 1, pos;
int head[maxn];
int deep[maxn], son[maxn], num[maxn], p[maxn], top[maxn], fa[maxn];

struct edge
{
	int v, next;
}Edge[maxn << 1];

void addedge(int a, int b)
{
	Edge[k].v = b;
	Edge[k].next = head[a];
	head[a] = k++;
}

void dfs1(int pos, int pre, int dep)
{
	deep[pos] = dep;
	num[pos] = 1;
	fa[pos] = pre;
	for (int i = head[pos]; i; i = Edge[i].next)
	{
		int v = Edge[i].v;
		if (v != pre)
		{
			dfs1(v, pos, dep + 1);
			num[pos] += num[v];
			if (son[pos] == -1 || num[son[pos]] < num[v])
				son[pos] = v;
		}
	}
}

void dfs2(int u, int pre, int v)
{
	top[u] = v;
	p[u] = ++pos;
	if (son[u] == -1) return;
	dfs2(son[u], u, v);
	for (int i = head[u]; i; i = Edge[i].next)
	{
		int v = Edge[i].v;
		if (v != pre&&v != son[u])
			dfs2(v, u, v);
	}
}

struct Node
{
	int l, r, tag;
	int Max, Min;
}cover[maxn << 2];

int n;

void build(int rt, int l, int r)
{
	cover[rt].l = l;
	cover[rt].r = r;
	cover[rt].tag = 0;
	cover[rt].Min = 0;
	cover[rt].Max = 0;
	if (l == r) return;
	int m = (l + r) >> 1;
	build(rt << 1, l, m);
	build(rt << 1 | 1, m + 1, r);
}

void qufan(int rt)
{
	int alt = -cover[rt].Max;
	cover[rt].Max = -cover[rt].Min;
	cover[rt].Min = alt;
}

void pushdown(int rt)
{
	if (cover[rt].tag)
	{
		if (cover[rt].tag % 2)
		{
			cover[rt << 1].tag++;
			cover[rt << 1 | 1].tag++;
			qufan(rt << 1);
			qufan(rt << 1 | 1);
		}
		cover[rt].tag = 0;
	}
}

void pushup(int rt)
{
	cover[rt].Min = min(cover[rt << 1].Min, cover[rt << 1 | 1].Min);
	cover[rt].Max = max(cover[rt << 1].Max, cover[rt << 1 | 1].Max);
}

void change(int rt, int pos, int l, int r, int val)
{
	if (l == r)
	{
		cover[rt].Max = cover[rt].Min = val;
		return;
	}
	pushdown(rt);
	int m = (l + r) >> 1;
	if (pos <= m) change(rt << 1, pos, l, m, val);
	else change(rt << 1 | 1, pos, m + 1, r, val);
	pushup(rt);
}

void reverse(int rt, int l, int r, int qstart, int qend)
{
	if (qstart <= l&&r <= qend)
	{
		cover[rt].tag++;
		qufan(rt);
		return;
	}
	pushdown(rt);
	int m = (l + r) >> 1;
	if (qstart <= m) reverse(rt << 1, l, m, qstart, qend);
	if (m < qend) reverse(rt << 1 | 1, m + 1, r, qstart, qend);
	pushup(rt);
}

int find(int rt, int l, int r, int qstart, int qend)
{
	//cout << 'l' << ' ' << l << ' ' << 'r' << ' ' << r << endl;
	if (qstart <= l&&r <= qend)
		return cover[rt].Max;
	pushdown(rt);
	int Ans=-inf,m = (l + r) >> 1;
	if (qstart <= m) Ans = max(Ans, find(rt << 1, l, m, qstart, qend));
	if (m < qend) Ans = max(Ans, find(rt << 1 | 1, m + 1, r, qstart, qend));
	return Ans;
}

int findmax(int u, int v)
{
	//cout << u << ' ' << v << endl;
	int tmp = -inf;
	int f1 = top[u], f2 = top[v];
	//cout << f1 << ' ' << f2 << endl;
	while (f1 != f2)
	{
		if (deep[f1] < deep[f2])
		{
			swap(u, v);
			swap(f1, f2);
		}
		tmp = max(tmp, find(1, 1, n, p[f1], p[u]));
		u = fa[f1], f1 = top[u];
	}
	if (u == v) return tmp;
	if (deep[u] > deep[v]) swap(u, v);
	//cout << 2 << endl;
	//cout << son[u] << endl;
	//cout << "p1" << ' ' << p[son[u]] << ' ' << "p2" << ' ' << p[v] << endl;
	return max(tmp, find(1, 1, n, p[son[u]], p[v]));
}

void Negate(int u, int v)
{
	int f1 = top[u], f2 = top[v];
	while (f1 != f2)
	{
		if (deep[f1] < deep[f2])
		{
			swap(u, v);
			swap(f1, f2);
		}
		reverse(1, 1, n, p[f1], p[u]);
		u = fa[f1], f1 = top[u];
	}
	if (u == v) return;
	if (deep[u] > deep[v]) swap(u, v);    //在同一条重链上但不在同一点
	reverse(1, 1, n, p[son[u]], p[v]);
}

int e[maxn][3];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		k = 1, pos = 0;
		memset(son, -1, sizeof(son));
		memset(head, 0, sizeof(head));
		cin >> n;

		for (int i = 1; i < n; i++)
		{
			cin >> e[i][0] >> e[i][1] >> e[i][2];
			addedge(e[i][0], e[i][1]);
			addedge(e[i][1], e[i][0]);
		}
		dfs1(1, 0, 0);
		dfs2(1, 0, 1);
		build(1, 1, n);
		for (int i = 1; i < n; i++)
		{
			if (deep[e[i][0]] > deep[e[i][1]])
				swap(e[i][0], e[i][1]);
			change(1, p[e[i][1]], 1, n, e[i][2]);
		}

		//cout << top[e[1][0]] << endl;
		//cout << top[e[3][1]]<<endl;
		char op[10];
		int u, v;
		while (cin >> op&&op[0] != 'D')
		{
			cin >> u >> v;
			if (op[0] == 'Q') cout << findmax(u, v) << endl;
			else
			{
				if (op[0] == 'N') Negate(u, v);
				else change(1, p[e[u][1]], 1, n, v);
			}
		}
	}
}