#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
inline int read()
{
    int ans = 0, f = 0;
    char c = getchar();
    while (!isdigit(c))
        f |= (c == '-'), c = getchar();
    while (isdigit(c))
        ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
    return f ? -ans : ans;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(48 + x % 10);
}
constexpr int N = 1e5 + 5;
int T, n, q;
vector<int> g[N];
struct tree
{
    int lc, rc, tot;
} t[N << 3];
int ad[N << 3];
#define mid (l + r >> 1)
#define len (r - l + 1)
inline void down(int p, int l, int r)
{
    if (ad[p])
    {
        t[p << 1].tot = len - (len >> 1) - 1;
        // t[p << 1].tot = (len >> 1) - 1;
        t[p << 1].lc = t[p << 1].rc = ad[p];
        t[p << 1 | 1].tot = (len >> 1) - 1;
        // t[p << 1 | 1].tot = (len >> 1) - 1;
        t[p << 1 | 1].lc = t[p << 1 | 1].rc = ad[p];
        ad[p << 1] = ad[p << 1 | 1] = ad[p];
        ad[p] = 0;
    }
}
void cover(int l, int r, int _s, int _t, int p, int w)
{
    if (l >= _s && r <= _t)
    {
        t[p].lc = t[p].rc = ad[p] = w;
        t[p].tot = len - 1;
        return;
    }
    down(p, l, r);
    if (mid >= _s)
        cover(l, mid, _s, _t, p << 1, w);
    if (mid < _t)
        cover(mid + 1, r, _s, _t, p << 1 | 1, w);
    t[p].lc = t[p << 1].lc, t[p].rc = t[p << 1 | 1].rc;
    t[p].tot = t[p << 1].tot + t[p << 1 | 1].tot + (t[p << 1].rc == t[p << 1 | 1].lc);
}
tree ask(int l, int r, int _s, int _t, int p)
{
    if (l >= _s && r <= _t)
        return t[p];
    down(p, l, r);
    tree ans;
    ans.lc = ans.rc = ans.tot = 0;
    if (mid >= _s)
        ans = ask(l, mid, _s, _t, p << 1);
    if (mid < _t)
    {
        tree t = ask(mid + 1, r, _s, _t, p << 1 | 1);
        if (!ans.lc)
            ans = t;
        else
        {
            ans.tot += t.tot + (ans.rc == t.lc);
            ans.rc = t.rc;
        }
    }
    return ans;
}
int d[N], fa[N], si[N], son[N];
int cnt, dfn[N], top[N];
void dfs1(int u, int ft)
{
    fa[u] = ft, d[u] = d[ft] + 1;
    si[u] = 1;
    for (int l = 0; l < g[u].size(); ++l)
    {
        int i = g[u][l];
        if (i != ft)
        {
            dfs1(i, u);
            si[u] += si[i];
            if (si[i] > si[son[u]])
                son[u] = i;
        }
    }
}
void dfs2(int u, int deep)
{
    top[u] = deep, dfn[u] = ++cnt;
    if (!son[u])
        return;
    dfs2(son[u], deep);
    for (int l = 0; l < g[u].size(); ++l)
    {
        int i = g[u][l];
        if (i != fa[u] && i != son[u])
            dfs2(i, i);
    }
}
int color;
inline int solve(int u, int v)
{
    int f = 1;
    // 1 : u
    // 0 : v
    tree l, r;
    l.lc = l.rc = l.tot = r.lc = r.rc = r.tot = 0;
    while (top[u] != top[v])
    {
        if (d[top[u]] < d[top[v]])
            swap(u, v), f ^= 1;
        tree t = ask(1, n, dfn[top[u]], dfn[u], 1);
        if (f)
            l = {l.lc, t.rc, l.tot + t.tot + (l.rc == t.lc)};
        else
            r = {t.lc, r.rc, r.tot + t.tot + (t.rc == r.lc)};
        u = fa[top[u]];
    }
    // if (d[u] > d[v])
    //     swap(u, v), f ^= 1;
    // tree t = ask(1, n, dfn[u], dfn[v], 1);
    if (d[u] < d[v])
        swap(u, v), f ^= 1;
    tree t = ask(1, n, dfn[v], dfn[u], 1);
    if (f)
        l = {l.lc, t.rc, l.tot + t.tot + (l.rc == t.lc)};
    else
        r = {t.lc, r.rc, r.tot + t.tot + (r.lc == t.rc)};
    return l.tot + r.tot + (l.rc == r.lc);
}
inline void change(int u, int v)
{
    ++color;
    while (top[u] != top[v])
    {
        if (d[top[u]] < d[top[v]])
            swap(u, v);
        cover(1, n, dfn[top[u]], dfn[u], 1, color);
        u = fa[top[u]];
    }
    if (d[u] > d[v])
        swap(u, v);
    cover(1, n, dfn[u], dfn[v], 1, color);
    return;
}
inline void init()
{
    cnt = 0, color = 0;
    memset(d, 0, sizeof d);
    memset(fa, 0, sizeof fa);
    memset(si, 0, sizeof si);
    memset(son, 0, sizeof son);
    memset(dfn, 0, sizeof dfn);
    memset(top, 0, sizeof top);
    memset(t, 0, sizeof t);
    memset(ad, 0, sizeof ad);
    for (int i = 1; i <= n; ++i)
        g[i].clear();
}
signed main()
{
    // freopen("P7735_2_copy.in", "r", stdin);
    // freopen(".out", "w", stdout);
    T = read();
    while (T--)
    {
        init();
        n = read(), q = read();
        for (int i = 1; i < n; ++i)
        {
            int u = read(), v = read();
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs1(1, 0);
        dfs2(1, 1);
        int col_init = 0;
        for (int i = 1; i <= n; ++i)
            cover(1, n, i, i, 1, --col_init);
        while (q--)
        {
            if (read() == 1)
                change(read(), read());
            else
            {
                write(solve(read(), read()));
                putchar('\n');
            }
        }
    }
    return 0;
}