轻重边

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define lowbit(u) (u&-u)
#define ls (p<<1)
#define rs (p<<1|1)
#define len(p) (t[p].e-t[p].s+1)
using namespace std;
const int mod=1e9+7,INF=0x3f3f3f3f3f3f3f3f;
struct edge
{int v,nxt;}e[200010];
struct tree{int l,r,cl,cr,sum,lz;}t[400010];
int T,n,m,tot,cnt;
int fa[100010],si[100010],son[100010],dep[100010];
int head[100010],dfn[100010],top[100010];
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read(void){
    int u(0),t(1);char fc(getchar());
    while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
    while(isdigit(fc)) u=(u<<1)+(u<<3)+(fc^48),fc=getchar();
    return u*t;
}
inline void print(int u)
{
	if(u<0) putchar('-'),u=-u;
	if(u>9) print(u/10);
	putchar(u%10+'0');
}
inline int ksm(int a,int b,int mod)
{
	int u=a%mod,res=1;
	while(b)
	{
		if(b&1) res=res*u%mod;
		b>>=1;u=u*u%mod;
	}
	return res;
}
void tclear(int p)
{
	t[p].cl=t[p].cr=t[p].lz=t[p].sum=0;
	if(t[p].l==t[p].r){t[p].l=t[p].r=0;return;}
	t[p].l=t[p].r=0;
	tclear(ls);tclear(rs);
}
void init()
{
	tot=cnt=0;
	memset(head,0,sizeof head);memset(fa,0,sizeof fa);
	memset(si,0,sizeof si);memset(son,0,sizeof son);
	memset(dep,0,sizeof dep);memset(dfn,0,sizeof dfn);
	memset(top,0,sizeof top);tclear(1);
}
void add(int u,int v){e[++tot].v=v;e[tot].nxt=head[u];head[u]=tot;}
void dfs1(int u,int ff)
{
	fa[u]=ff,si[u]=1,dep[u]=dep[ff]+1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==ff) continue;
		dfs1(v,u);si[u]+=si[v];
		if(si[v]>si[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int topf)
{
	top[u]=topf,dfn[u]=++cnt;
	if(son[u]) dfs2(son[u],topf);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void pushdown(int p)
{
	if(!t[p].lz)return;int mid=(t[p].l+t[p].r)>>1;
	t[ls].lz=t[rs].lz=t[p].lz;
	t[ls].cl=t[ls].cr=t[rs].cl=t[rs].cr=t[p].lz;
	t[ls].sum=mid-1,t[rs].sum=t[p].r-mid-1,t[p].lz=0;
}
void update(int p,int l,int r,int x)
{
	if(t[p].l>=l&&t[p].r<=r)
	{
		t[p].cl=t[p].cr=t[p].lz=x;
		t[p].sum=t[p].r-t[p].l;return;
	}pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) update(ls,l,r,x);
	if(r>mid) update(rs,l,r,x);
	t[p].cl=t[ls].cl;t[p].cr=t[rs].cr;t[p].sum=t[ls].sum+t[rs].sum+(t[ls].cr==t[rs].cl);
}
tree query(int p,int l,int r)
{
	if(t[p].l>=l&&t[p].r<=r) return t[p];
	int mid=(t[p].l+t[p].r)>>1,res=0;pushdown(p);tree res1=(tree){0,0,0,0,0,0},res2=(tree){0,0,0,0,0,0};
	if(mid>=l) res+=1,res1=query(ls,l,r);
	if(mid<r) res+=2,res2=query(rs,l,r);
	if(res==1) return res1;if(res==2) return res2;
	return (tree){0,0,res1.cl,res2.cr,res1.sum+res2.sum+(res1.cr==res2.cl),0};
}
void mobify(int x,int y,int num)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update(1,dfn[top[x]],dfn[x],num);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	update(1,dfn[y],dfn[x],num);
}
int lca(int x,int y)
{
	bool flag=0;
	tree h,ans1=(tree){0,0,0,0,0,0},ans2=(tree){0,0,0,0,0,0};
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) flag=!flag,swap(x,y);
		h=query(1,dfn[top[x]],dfn[x]);
		if(flag) ans2=(tree){0,0,h.cl,ans2.cr,ans2.sum+h.sum+(ans2.cl==h.cr),0};
		else ans1=(tree){0,0,ans1.cl,h.cl,ans1.sum+h.sum+(ans1.cr==h.cr),0};
		x=fa[top[x]];
	}
	if(dep[x]<dep[y]) swap(x,y),flag=!flag;
	h=query(1,dfn[y],dfn[x]);
	if(flag) ans2=(tree){0,0,h.cl,ans2.cr,ans2.sum+h.sum+(ans2.cl==h.cr),0};
	else ans1=(tree){0,0,ans1.cl,h.cl,ans1.sum+h.sum+(ans1.cr==h.cr),0};
	return ans1.sum+ans2.sum+(ans1.cr==ans2.cl);
}
signed main()
{
	T=read();
	while(T--)
	{
		n=read(),m=read();
		for(int i=1,u,v;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);
		dfs1(1,0),dfs2(1,1);build(1,1,n);
		for(int i=1;i<=n;i++) update(1,dfn[i],dfn[i],-dfn[i]);
		for(int i=1,op,u,v;i<=m;i++)
		{
			op=read(),u=read(),v=read();
			if(op==1) mobify(u,v,i);
			else print(lca(u,v)),puts("");
		}
		init();
	}
	return 0;
}