思路就是像染色一样每次染一条链，询问的时候分成 x->lca 和 (lca->y的下一级祖先) -> y，然后中间拼一下，但是不知道为什么挂了很多，答案里错的都是和正确的相差 1 或者 2，调不出来，球球。

去掉了文件头和快读等不必要的影响

int n, Cols, Q;

struct edges{
	int nxt, ver;
}edge[N << 1];

int head[N] ,tot;
inline void add(int a, int b)
{
	edge[++ tot] = {head[a], b};
	head[a] = tot;
}

int fa[N], sze[N], son[N], dep[N];
void get_son(int x, int Fa)
{
	fa[x] = Fa;
	sze[x] = 1;
	dep[x] = dep[Fa] + 1;
	for(int i = head[x]; i; i = edge[i].nxt)
	{
		int y = edge[i].ver;
		if(y == Fa)	 continue;
		get_son(y, x);
		sze[x] += sze[y];
		sze[son[x]] < sze[y] ? son[x] = y : y = y;
	}
}

int top[N], cnt, dfn[N], nfd[N];
void get_chain(int x, int Top)
{
	top[x] = Top;
	dfn[x] = ++ cnt;
	nfd[cnt] = x;
	if(!son[x])	 return;
	get_chain(son[x], Top);
	for(int i = head[x]; i ; i = edge[i].nxt)
	{
		int y = edge[i].ver;
		if(y == son[x] or y == fa[x])	 continue;
		get_chain(y, y);
	}
}

inline int LCA(int x, int y)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]])	swap(x, y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

struct Seg{
	int l, r, lc, rc, sum, tag;
	#define l(p)	tree[p].l
	#define r(p)	tree[p].r
	#define lc(p)	tree[p].lc
	#define rc(p)	tree[p].rc
	#define tag(p)	tree[p].tag
	#define sum(p)	tree[p].sum
}tree[N << 2];

void build(int p, int l, int r)
{
	l(p) = l, r(p) = r, tag(p) = 0, lc(p) = 0, rc(p) = 0, sum(p) = 0;
	if(l == r)
	{
		lc(p) = rc(p) = dfn[l];
		sum(p) = 0;
		return ;
	}
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}

inline void Spread(int p)
{
	if(tag(p))
	{
		lc(p << 1) = lc(p << 1 | 1) = tag(p);
		rc(p << 1) = rc(p << 1 | 1) = tag(p);
		
		sum(p << 1) = r(p << 1) - l(p << 1);
		sum(p << 1 | 1) = r(p << 1 | 1) - l(p << 1 | 1);
		
		tag(p << 1) = tag(p << 1 | 1) = tag(p);
		tag(p) = 0;
	}
}

inline void update(int p)
{
	lc(p) = lc(p << 1), rc(p) = rc(p << 1 | 1);
	sum(p) = sum(p << 1) + sum(p << 1 | 1) + (lc(p << 1 | 1) == rc(p << 1));
}

void mtf(int p, int l, int r, int c)
{
	if(l(p) >= l and r(p) <= r)
	{
		tag(p) = c;
		sum(p) = r(p) - l(p);
		lc(p) = rc(p) = c;
		return;
	}
	Spread(p);
	int mid = l(p) + r(p) >> 1;
	if(l <= mid)	mtf(p << 1,l , r, c);
	if(r > mid)		mtf(p << 1 | 1, l, r, c);
	update(p);
}

struct area { int lc, rc, sum; };

area qry(int p, int l, int r) // 我关注的只有左端点，右端点 
{
	if(l(p) >= l and r(p) <= r)	return {lc(p), rc(p), sum(p)};
	Spread(p);
	int mid = l(p) + r(p) >> 1;
	area Val = {0, 0, 0};
	if(l <= mid)	Val = qry(p << 1, l, r);
	if(r > mid)
	{
		area Right = qry(p << 1 | 1, l, r);
		if(Val.lc)// 有左区间	
		{
			Val.sum += Right.sum + (Val.rc == Right.lc);
			Val.rc = Right.rc;
		}
		else	Val = Right;
	}
	return Val;
}

void ch_mtf(int x, int y, int c)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]])	swap(x, y);
		mtf(1, dfn[top[x]], dfn[x], c);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])	 swap(x, y);
	mtf(1, dfn[x], dfn[y], c);
}

#define pb emplace_back
vector<area> ls, rs;

// 由于链需要跨过 lca，我用了个分讨，跨过 lca 的我分成向上为左链， dep 大的为该链左边，右链相反

void ch_qry(int x, int lca, bool op) // 假如是两条链拼在一起，1 表示左链，0 表示右链 
{
	while(top[x] != top[lca])
	{
		area blo = qry(1, dfn[top[x]], dfn[x]);
		op ? ls.pb((area){blo.rc, blo.lc, blo.sum}) : rs.pb(blo);
		x = fa[top[x]];
	}
	area blo = qry(1, dfn[lca], dfn[x]);
	op ? ls.pb((area){blo.rc, blo.lc, blo.sum}) : rs.pb(blo);
}

inline int jmp(int x, int lca) // 下一级祖先
{
	while(top[x] != top[lca])
	{
		if(fa[top[x]] == lca)	return top[x];
		x = fa[top[x]];
	}
	return nfd[dfn[lca] + 1];
}

int ch_cut(int x, int y) // 记住,左链从前向扫，右链从后向前扫 
{
	int lca = LCA(x, y), Ans = 0;
	int jp = jmp(y, lca);
	
	if(lca == x or lca == y)
	{
		if(dep[x] < dep[y])	 swap(x, y);
		ch_qry(x, y, 1);
	}
	
	else	ch_qry(x, lca, 1), ch_qry(y, jp, 0); // 右边只让跳到 jp 
	Ans += ls[0].sum;
	
	for(int i = rs.size() - 1;i >= 0; -- i)
		ls.pb(rs[i]), rs.pop_back();
	
	for(int i = 1;i < ls.size();i = -~i)
		Ans += ls[i].sum + (ls[i - 1].rc == ls[i].lc);
	
	for(int i = ls.size() - 1;i >= 0; -- i)
		ls.pop_back(); // 清空
	
	return Ans; 
}

inline void work()
{
	n = read(), Q = read();
	for(int i = 1;i < n;i = -~i)
	{
		int a = read(), b = read();
		add(a, b), add(b, a);
	}
	
	get_son(1, 1);
	get_chain(1, 1);
	build(1, 1, n);
	
	Cols = n;
	while(Q --)
	{
		int op = read();
		if(op == 1)
		{
			int x = read(), y = read();
			ch_mtf(x, y, ++ Cols);
		}
		else
		{
			int x = read(), y = read();
			printf("%lld\n", ch_cut(x, y));
		}
	}
}

inline void clears()
{
	memset(head, 0, sizeof head);
	memset(sze, 0, sizeof sze);
	memset(son, 0, sizeof son);
	memset(dep, 0, sizeof dep);
	cnt = 0, tot = 0, Cols = 0;
}

signed main()
{
	int T = read();
	while(T --)
	{
		work();
		clears();
	}
	return 0;
}