只 TLE 最后一个点，时间 1.1s ~ 1.2s。

#include <bits/stdc++.h>
using namespace std;

inline void train() {
	   ios::sync_with_stdio(false);
	   cin.tie(0);
	   cout.tie(0);
}

inline int maxi(int a, int b) {
	return a > b ? a : b;
}

inline int mini(int a, int b) {
	return a < b ? a : b;
}

// As long as I believe this is correct.
constexpr int N = 1e5+3, NS = 4e5+3, BAD = -3e7;
vector<int> tree[N];
int lrange[NS], rrange[NS], val[NS], lazy[NS], lmost[NS], lens[NS], rmost[NS], n, m;
bool has_lazy[NS];
int sz[N], hat[N], htop[N], dfn[N], depth[N], father[N], dfid = 0;
bool is_heavy[N];

#define lch (root<<1)
#define rch ((root<<1)|1)
#define mids() int mid = (lrange[root] + rrange[root]) >> 1
#define lcall lch, maxi(lrange[root], l), mini(mid, r)
#define rcall rch, maxi(mid+1, l), mini(rrange[root], r)

void dfs1(int cur, int fa) {
	sz[cur] = 1;
	depth[cur] = depth[fa] + 1;
	int maxat = 0, maxval = 0;
	for (auto &i : tree[cur]) {
		if (i == fa) continue;
		dfs1(i, cur);
		sz[cur] += sz[i];
		if (sz[i] > maxval) {
			maxval = sz[i];
			maxat = i;
		}
	}
//	cerr << "heavy selection of " << cur << " is " << maxat << endl;
	hat[cur] = maxat;
	is_heavy[maxat] = true;
}

void dfs2(int cur, int fa) {
	dfn[cur] = (++dfid);
	father[cur] = fa;
	if ((cur == fa) || (!is_heavy[fa])) htop[cur] = cur;
	else if (is_heavy[cur]) htop[cur] = htop[fa];
	else htop[cur] = cur;
//	cerr << "chain-top at " << cur << " is " << htop[cur] << endl;
	if (hat[cur]) dfs2(hat[cur], cur);
	for (auto &i : tree[cur]) {
		if (i == fa || i == hat[cur]) continue;
		dfs2(i, cur);
	}
}

inline int length(int root) {
	return lens[root];
}

inline void modify(int root, int value) {
	val[root] = length(root) - 1;
	lmost[root] = rmost[root] = lazy[root] = value;
	has_lazy[root] = true;
}

inline void pushup(int root) {
	val[root] = val[lch] + val[rch];
	lmost[root] = lmost[lch];
	rmost[root] = rmost[rch];
	if (lmost[rch] == rmost[lch]) val[root]++;
}

void build(int root, int l, int r) {
//	cerr << "build(" << root << "," << l << "," << r << ")\n";
	if (l > r) return;
	lrange[root] = l;
	rrange[root] = r;
	lens[root] = r-l+1;
	has_lazy[root] = false;
	if (l == r) {
		modify(root, -l);	// Ensuring unique color.
		return;
	}
	mids();
	build(lch, l, mid);
	build(rch, mid+1, r);
	pushup(root);
}

void pushdown(int root) {
	if (has_lazy[root]) {
		modify(lch, lazy[root]);
		modify(rch, lazy[root]);
		has_lazy[root] = false;
	}
}

void update(int root, int l, int r, int value) {
	if (l > r) return;
	if (lrange[root] >= l && rrange[root] <= r) {
		modify(root, value);
		return;
	}
	pushdown(root);
	mids();
	update(lcall, value); update(rcall, value);
	pushup(root);
}

struct qinfo {
	int value, lmost, rmost;
	qinfo() : value(0), lmost(BAD), rmost(BAD) {
		
	}
	qinfo(int value, int lmost, int rmost) : value(value), lmost(lmost), rmost(rmost) {
		
	}
};

inline qinfo operator + (const qinfo &lres, const qinfo &rres) {
	if (lres.lmost == BAD || lres.rmost == BAD) return rres;
	if (rres.lmost == BAD || rres.rmost == BAD) return lres;
	qinfo ans;
	ans.value = lres.value + rres.value;
	if (lres.rmost > BAD && rres.lmost > BAD && lres.rmost == rres.lmost) ans.value++;
	ans.lmost = ((lres.lmost <= BAD) ? rres.lmost : lres.lmost);
	ans.rmost = ((rres.rmost <= BAD) ? lres.rmost : rres.rmost);
	return ans;
}

qinfo query(int root, int l, int r) {
	if (l > r) return qinfo();
	if (lrange[root] >= l && rrange[root] <= r) return qinfo(val[root], lmost[root], rmost[root]);
	pushdown(root);
	mids();
	return query(lcall) + query(rcall);
}
/*
int lca(int x, int y) {
	while (htop[x] != htop[y]) {
		if (depth[htop[x]] < depth[htop[y]]) swap(x, y);
		x = father[htop[x]];
	} 
	if (depth[x] < depth[y]) return x;
	else return y;
}
*/

inline void _swap(int &a, int &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

#define swap _swap

using ll = long long;
inline ll read(ll x=0,bool f=0,char c=getchar()) {while(!isdigit(c)) f=c=='-',c=getchar();while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();return f?-x:x;};
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

void subgroup() {

//	cin>>n>>m;
	n = read(); m = read();
	dfid = 0;

	build(1, 1, n);
	for (int i = 0; i < n-1; i++) {
		int a = read(),b = read();
// 		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs1(1, 1);
	is_heavy[1] = true;
	dfs2(1, 1);
//	cerr << "end of tree construction.\n";
	for (int qs = 1; qs <= m; qs++) {
		int op, a, b;
//		cin>>op>>a>>b;
		op = read(); a = read(); b = read();
		
		if (op == 1) {
			
			while (htop[a] != htop[b]) {
				if (depth[htop[a]] < depth[htop[b]]) swap(a, b);
//				cerr << "update " << htop[a] << "--" << a << " as " << qs << endl;
				update(1, dfn[htop[a]], dfn[a], qs);
				a = father[htop[a]];
			}
			
			if (depth[a] > depth[b]) swap(a, b);
//			cerr << "update " << a << "--" << b << endl;
			update(1, dfn[a], dfn[b], qs);
			
		} else {
		
			qinfo ajump = qinfo(), bjump = qinfo();
			while (htop[a] != htop[b]) {
				if (depth[htop[a]] > depth[htop[b]]) {
					qinfo tmp = query(1, dfn[htop[a]], dfn[a]);
					swap(tmp.lmost, tmp.rmost);
//					cerr << "temp: " << tmp.value << " <" << tmp.lmost << "|" << tmp.rmost << "> (post-swap)\n";
					ajump = ajump + tmp;
//					cerr << htop[a] << " -A- " << a << " accu. " << ajump.value << " <" << ajump.lmost << "|" << ajump.rmost << ">\n";
					a = father[htop[a]];
				} else {
					bjump = query(1, dfn[htop[b]], dfn[b]) + bjump;
//					cerr << htop[b] << " -B- " << b << " accu. " << bjump.value << " <" << bjump.lmost << "|" << bjump.rmost << ">\n";
					b = father[htop[b]];
				}
			}
			qinfo rjump, ans;
			if (depth[a] < depth[b]) {
				rjump = query(1, dfn[a], dfn[b]);
//				cerr << "A higher\n";
			}
			else {
//				cerr << "B higher\n";
				rjump = query(1, dfn[b], dfn[a]);
				swap(rjump.lmost, rjump.rmost);
			}
//			cerr << "major merge " << rjump.value << " <" << rjump.lmost << "|" << rjump.rmost << ">\n";
//			auto ar = ajump + rjump, rb = rjump + bjump;
			ans = ajump + rjump + bjump;
//			cerr << "AR = " << ar.value << " <" << ar.lmost << "|" << ar.rmost << ">\n";
//			cerr << "RB =  "<< rb.value << " <" << rb.lmost << "|" << rb.rmost << ">\n";
//			cout<<ans.value<<'\n';
//			printf("%d\n", ans.value); 
			write(ans.value);
			putchar('\n');
		}
		
	}
	for (int i = 1; i <= n; i++) {
		depth[i] = hat[i] = 0;
		is_heavy[i] = false;
		tree[i].clear();
		//tree[i].reserve(128);
	}
//	cout<<flush;
//	cerr << "End of group.\n";
}

int main() {
//#ifdef ONLINE_JUDGE
//	train();
//#endif
	int t = read();
//	cin>>t;
	for (int i = 0; i < t; i++) subgroup();
//	cout<<flush;
	return 0;
}