RT/kel

// Problem: P7735 [NOI2021] 轻重边
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7735
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define inl inline
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
using namespace std;
const int N=1e5+10;
struct Node{
	int v,lc,rc;
}t[N<<2];
int lazy[N<<2],w[N],fa[N],dep[N],sz[N],sn[N],top[N],rnk[N],dfn[N],cnt,v,n,m;
vector<int>e[N];
namespace Tree{
	#define ls k<<1
	#define rs k<<1|1
	#define mid (l+r>>1)
	#define pushup(k) t[k]=(Node){t[ls].v+t[rs].v+(t[ls].rc==t[rs].lc),t[ls].lc,t[rs].rc};
	inl void pushdown(int k,int l,int r){
		if(!lazy[k])return ;
		lazy[ls]=lazy[rs]=lazy[k];t[ls]=(Node){mid-l,lazy[k],lazy[k]};
		t[rs]=(Node){r-mid-1,lazy[k],lazy[k]};lazy[k]=0;
	}
	inl void build(int k,int l,int r){
		if(l==r){t[k]=(Node){0,rnk[l],rnk[l]};return ;}
		build(ls,l,mid);build(rs,mid+1,r);pushup(k);
	}
	inl void update(int k,int l,int r,int x,int y,int v){
		if(x>r||y<l)return ;
		if(x<=l&&y>=r){t[k]=(Node){r-l,v,v};lazy[k]=v;return;}
		pushdown(k,l,r);update(ls,l,mid,x,y,v);update(rs,mid+1,r,x,y,v);pushup(k);
	}
	inl int query(int k,int l,int r,int x,int y){
		if(x>r||y<l)return 0;
		if(x<=l&&y>=r)return t[k].v;
		pushdown(k,l,r);return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y)+(l<=mid&&r>mid&&t[ls].rc==t[rs].lc);
	}
	inl int query2(int k,int l,int r,int x){
		if(l==r)return t[k].lc;
		pushdown(k,l,r);
		if(x<=mid)return query2(ls,l,mid,x);
		else return query2(rs,mid+1,r,x);
	}
}
using namespace Tree;
namespace Chain{
	inl void dfs1(int u,int pre){
		sz[u]=1;
		rep(i,1,e[u].size()-1){
			int v=e[u][i];
			if(v==pre)continue;
			dep[v]=dep[u]+1;fa[v]=u;dfs1(v,u);sz[u]+=sz[v];
			if(sz[v]>sz[sn[u]])sn[u]=v;
		}
	}
	inl void dfs2(int u,int t){
		top[u]=t;
		dfn[u]=++cnt;
		rnk[cnt]=w[u];
		if(sn[u])dfs2(sn[u],t);
		rep(i,0,e[u].size()-1){
			int v=e[u][i];
			if(v==fa[u]||v==sn[u])continue;
			dfs2(v,v);
		}
	}
	inl void upd(int x,int y){
		v++;int fx=top[x],fy=top[y];
		while(fx!=fy){
			if(dep[fx]<dep[fy]){swap(fx,fy);swap(x,y);}
			update(1,1,n,dfn[fx],dfn[x],v);
			x=fa[fx];fx=top[x];
		}
		if(dep[x]>dep[y])swap(x,y);
		update(1,1,n,dfn[x],dfn[y],v);
	}
	inl int que(int x,int y){
		int fx=top[x],fy=top[y],ans=0;
		while(fx!=fy){
			if(dep[fx]<dep[fy]){swap(fx,fy);swap(x,y);}
			ans+=query(1,1,n,dfn[fx],dfn[x]);
			ans+=query2(1,1,n,dfn[fx])==query2(1,1,n,dfn[fa[fx]]);
			x=fa[fx];fx=top[x];
		}
		if(dep[x]>dep[y])swap(x,y);
		return ans+query(1,1,n,dfn[x],dfn[y]);
	}
}
using namespace Chain;
signed main(void){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--){
		cin>>n>>m;
		v=cnt=0;
		memset(fa,0,sizeof(fa));memset(dep,0,sizeof(dep));memset(sz,0,sizeof(sz));memset(sn,0,sizeof(sn));
		memset(top,0,sizeof(top));memset(rnk,0,sizeof(rnk));memset(lazy,0,sizeof(lazy));
		rep(i,1,n-1){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}
		dfs1(1,0);dfs2(1,1);
		rep(i,1,n)w[i]=++v;
		while(m--){
			int op,x,y;cin>>op>>x>>y;
			if(op==2)upd(x,y);
			else cout<<que(x,y)<<'\n';
		}
	}
	rep(i,1,n)e[i].clear();
}