rt,写的五十分暴力，不知道错哪了快疯了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 5005, logn = 14;
int n, m, t, op, a, b, s, de[N], fa[N], f[N][logn];
struct edge {
	int to, c;
};
vector<edge> e[N];
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	return x * f;
}
void dfs(int u) {
	for (int i = 0; i < e[u].size(); i++) {
		int v = e[u][i].to;
		if (v == fa[u]) continue;
		de[v] = de[u] + 1;
		fa[v] = u;
		dfs(v);
	}
	return;
}
inline int lca(int x, int y) {
	if (de[x] < de[y]) swap(x, y);
	for (int i = 0, p = de[x] - de[y]; p; i++, p >>= 1)
		if (p & 1) x = f[x][i];
	if (x == y) return x;
	for (int j = logn; j >= 0; j--)
		if (f[x][j] != f[y][j]) x = f[x][j], y = f[y][j];
	return f[x][0];
}
inline void slove(int u) {
	for (int i = 0; i < e[u].size(); i++) {
		if (e[u][i].to == fa[u]) e[u][i].c = 1;
		else e[u][i].c = 0;
	}
	return;
}
inline void modifly(int x, int y, int g) {
	int i, j;
	for (i = x; fa[i] != g; i = fa[i]) slove(i);
	for (j = y; fa[j] != g; j = fa[j]) slove(j);
	slove(i), slove(j);
	for (int h = 0; h < e[g].size(); h++) {
		if (e[g][h].to == i || e[g][h].to == j) e[g][h].c = 1;
		else e[g][h].c = 0;
	}
	return;
}
inline int query(int x, int y, int g) {
	int res = 0;
	for (int i = x; i != g; i = fa[i])
		for (int j = 0; j < e[i].size(); j++)
			if (e[i][j].to == fa[i]) res += e[i][j].to;
	for (int i = y; i != g; i = fa[i])
		for (int j = 0; j < e[i].size(); j++)
			if (e[i][j].to == fa[i]) res += e[i][j].to;
	return res;
}
int main() {
	t = read();
	while (t--) {
		n = read(), m = read();
		for (int i = 1, u, v; i < n; i++)
			u = read(), v = read(),
			e[u].push_back((edge) {
			v, 0
		}),
		e[v].push_back((edge) {
			u, 0
		});
		dfs(1);
		for (int i = 1; i <= n; i++) f[i][0] = fa[i];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= logn; j++)
				f[i][j] = f[f[i][j - 1]][j - 1];
		while (m--) {
			op = read(), a = read(), b = read(), s = lca(a, b);
			if (op == 1) modifly(a, b, s);
			else cout << query(a, b, s) << endl;
		}
		for (int i = 1; i <= n; i++) e[i].clear(), fa[i] = 0, de[i] = 0;
	}
	return 0;
}