#include<bits/stdc++.h>

using namespace std;

struct node{
	vector<int> nxt;
	int father;
	int deep;
	int size;
	int heavyson;
	
	int dfn;
	int top;
};

vector<node> tree;

void dfs1(int now){
	tree[now].size=1;
	for(auto i:tree[now].nxt){
		if(i==tree[now].father){
			continue;
		}
		tree[i].father=now;
		tree[i].deep=tree[now].deep+1;
		dfs1(i);
		tree[now].size+=tree[i].size;
		if(tree[i].size>tree[tree[now].heavyson].size){
			tree[now].heavyson=i;
		}
	}
}

int dfncnt=0;

void dfs2(int now){
	tree[now].dfn=++dfncnt;
	if(tree[tree[now].father].heavyson==now){
		tree[now].top=tree[tree[now].father].top;
	}
	else{
		tree[now].top=now;
	}
	if(tree[now].heavyson!=0){
		dfs2(tree[now].heavyson);
	}
	for(auto i:tree[now].nxt){
		if(i!=tree[now].father&&i!=tree[now].heavyson){
			dfs2(i);
		}
	}
}

int lca(int u,int v){
	while(tree[u].top!=tree[v].top){
		if(tree[tree[u].top].deep<tree[tree[v].top].deep){
			swap(u,v);
		}
		u=tree[tree[u].top].father;
	}
	if(tree[u].deep>tree[v].deep){
		swap(u,v);
	}
	return u;
}

int Top(int u,int fa){
	while(1){
		if(tree[u].father==fa){
			return u;
		}
		else if(tree[u].top==tree[fa].top){
			return tree[fa].heavyson;
		}
		u=(u==tree[u].top?tree[u].father:tree[u].top);
	}
}

int n,m;

struct Base{
	int lc;
	int rc;
	int sum;
	
	void on(int c,int len){
		lc=rc=c;
		sum=len-1;
	}
	Base(int c){
		lc=rc=c;
		sum=1;
	}
	Base(){lc=rc=-1,sum=0;}
};

Base merge(Base a,Base b){
	Base tmp;
	tmp.lc=a.lc;
	tmp.rc=b.rc;
	tmp.sum=a.sum+b.sum+(a.rc==b.lc);
	return tmp;
}

struct segtree{
	struct node{
		Base value;
		int tag;
		
		node(){
			tag=-1;
		}
		
		void on(int c,int len){
			value.on(c,len);
			tag=c;
		}
	};
	
	vector<node> work;
	
	void build(int now,int l,int r){
		if(l==r){
			work[now].on(l,1);
			return;
		}
		int mid=(l+r)>>1;
		build(now<<1,l,mid);
		build(now<<1|1,mid+1,r);
		work[now].value=merge(work[now<<1].value,work[now<<1|1].value);
	}
	
	void pushdown(int now,int len){
		if(work[now].tag!=-1){
			int mid=(len+1)>>1;
			work[now<<1].on(work[now].tag,mid);
			work[now<<1|1].on(work[now].tag,len-mid);
			work[now].tag=-1;
		}
	}
	
	void update(int now,int from,int to,int ql,int qr,int v){
		if(from==ql&&qr==to){
			work[now].on(v,to-from+1);
			return;
		}
		pushdown(now,to-from+1);
		int mid=(from+to)>>1;
		if(ql<=mid){
			update(now<<1,from,mid,ql,min(qr,mid),v);
		}
		if(mid<qr){
			update(now<<1|1,mid+1,to,max(ql,mid+1),qr,v);
		}
		work[now].value=merge(work[now<<1].value,work[now<<1|1].value);
	}
	
	Base ask(int now,int from,int to,int ql,int qr){
		if(from==ql&&qr==to){
			return work[now].value;
		}
		pushdown(now,to-from+1);
		int mid=(from+to)>>1;
		if(qr<=mid){
			return ask(now<<1,from,mid,ql,qr);
		}
		else if(ql>mid){
			return ask(now<<1|1,mid+1,to,ql,qr);
		}
		else{
			return merge(ask(now<<1,from,mid,ql,mid),ask(now<<1|1,mid+1,to,mid+1,qr));
		}
	}
	
	void init(){
		work.clear();
		work.resize(4*n+5);
		build(1,1,n);
	}
};

segtree work;
int nowcnt=n;

void update(int u,int v){
	nowcnt++;
	while(tree[u].top!=tree[v].top){
		if(tree[tree[u].top].deep<tree[tree[v].top].deep){
			swap(u,v);
		}
		work.update(1,1,n,tree[tree[u].top].dfn,tree[u].dfn,nowcnt);
		u=tree[tree[u].top].father;
	}
	if(tree[u].deep>tree[v].deep){
		swap(u,v);
	}
	work.update(1,1,n,tree[u].dfn,tree[v].dfn,nowcnt);
}

Base ask(int u,int v){
	int l=lca(u,v);
	if(tree[u].deep<tree[v].deep){
		swap(u,v);
	}
	if(l==v){
		Base now;
		now.lc=-1;
		while(tree[u].top!=tree[v].top){
			if(now.lc==-1){
				now=work.ask(1,1,n,tree[tree[u].top].dfn,tree[u].dfn);
			}
			else{
				now=merge(work.ask(1,1,n,tree[tree[u].top].dfn,tree[u].dfn),now);
			}
			u=tree[tree[u].top].father;
		}
		now=merge(work.ask(1,1,n,tree[v].dfn,tree[u].dfn),now);
		return now;
	}
	Base u1=ask(u,l);
	Base u2=ask(v,Top(v,l));
	Base ret;
	ret.sum=-1;
	ret.sum=u1.sum+u2.sum+(u1.lc==u2.lc);
	return ret;
}

void solve(){
#ifdef tree_debug
	tree.clear();
	cin>>n;
	work.init();
	dfncnt=n;
	int op;
	while(cin>>op){
		int l,r;
		cin>>l>>r;
		if(op==1){
			work.update(1,1,n,l,r,++dfncnt);
		}
		else{
			cout<<work.ask(1,1,n,l,r).sum<<"\n";
		}
	}
	return;
#else
	tree.clear();
	cin>>n>>m;
	work.init();
	dfncnt=0;
	nowcnt=n;
	tree.resize(n+1);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		tree[u].nxt.push_back(v);
		tree[v].nxt.push_back(u);
	}
	dfs1(1);
	dfs2(1);
	while(m--){
		int op,u,v;
		cin>>op>>u>>v;
		if(op==1){
			update(u,v);
		}
		else{
			cout<<ask(u,v).sum<<"\n";
		}
	}
#endif
}

signed main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}