#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,head[N],num,dis[N],dep[N],k,g,vv;
struct node{
    int nxt,to,dis;
}e[N<<1];
struct trie{
    int tr[N*32][2],cnt;
    map<pair<int,int>,bool> ed;
    void insert(int x){
        int now=0;
        for(int i=31;i>=0;i--){
            int c=((x>>i)&1);
            if(!tr[now][c])tr[now][c]=++cnt;
            now=tr[now][c];
        }
        ed[mp(now,vv)]=true;
    }
    int query(int now,int x,int dep,int sum){
        if(dep==-1){
            if(ed[mp(now,vv)])return -1;
            return sum;
        }
        int c=(x>>dep)&1;
        if(tr[now][c^1]){
            int ans=query(tr[now][c^1],x,dep-1,sum+(1<<dep));
            if(ans!=-1)return ans;
        }
        if(tr[now][c])return query(tr[now][c],x,dep-1,sum);
        return -1;
    }
}T0,T1;
void add(int x,int y,int z){
    e[++num]=node{head[x],y,z};head[x]=num;
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dis[v]=dis[u]^e[i].dis;
        dfs(v,u);
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        cin>>n>>m;k=0;
        for(int i=1;i<n;i++){
            int x,y,z;scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);add(y,x,z);
        }dfs(1,0);
        for(int i=1;i<=n;i++){
            vv=i;
            if(dep[i]%2==0)T1.insert(dis[i]);
            else T0.insert(dis[i]);
        }
        while(m--){
            char op;
            int x,y;
            cin>>op>>x;vv=x;
            if(op=='^')k^=x;
            else{
                cin>>y;
                g=y^dis[x];
                if(dep[x]%2==0)g^=k;
                int w=max(T0.query(0,g,31,0),T1.query(0,g^k,31,0));
                if(w==3&&t==0)cout<<"10 ";
                else cout<<w<<" ";
            }
        }puts("");
        for(int i=1;i<=n;i++)dis[i]=0,head[i]=0;num=0;
        for(int i=0;i<=T0.cnt;i++)T0.tr[i][0]=T0.tr[i][1]=0,T0.ed.clear();T0.cnt=0;
        for(int i=0;i<=T1.cnt;i++)T1.tr[i][0]=T1.tr[i][1]=0,T1.ed.clear();T1.cnt=0;
    }
    return 0;
}