我知道恶心的树剖没人看，但我还是不想放弃调了两天的树剖：

#include<bits/stdc++.h>
using namespace std;
int T;
int t;
int jd[100010];
struct P
{
    vector<int>son;
    int siz;
    int bg;
    int en;
    int fa;
    int top;
    int dep;
    int hson;
    int dfn;
}p[100010];
struct xds
{
    int l;
    int r;
    int sum;
    int tag;
}x[400010];
void dfs(int x,int fa)
{
    p[x].dep=p[fa].dep+1;
    p[x].fa=fa;
    p[x].siz=1;
    for(int i=0;i<p[x].son.size();++i)
        if(p[x].son[i]!=fa)
        {
            dfs(p[x].son[i],x);
            p[x].siz+=p[p[x].son[i]].siz;
            if(p[p[x].son[i]].siz>p[p[x].hson].siz)
                p[x].hson=p[x].son[i];
        }
}
void lscl(int x,vector<int>&mm)
{
    p[x].top=p[p[x].fa].top;
    p[x].dfn=++t;
    jd[t]=x;
    int tb=mm.size();
    p[x].en=p[p[x].fa].en;
    for(int i=0;i<p[x].son.size();++i)
        if(p[x].son[i]!=p[x].fa&&p[x].son[i]!=p[x].hson)
        {
            p[x].en=p[x].son[i];
            if(!p[x].bg)p[x].bg=p[x].son[i];
            mm.push_back(p[x].son[i]);
        }
    if(p[x].hson)
    {
        lscl(p[x].hson,mm);
        if(!p[x].bg)p[x].bg=p[p[x].hson].bg;
    }
}
void ltcl(int x)
{
    vector<int>mm;
    p[x].top=x;
    for(int i=0;i<p[x].son.size();++i)
        if(p[x].son[i]!=p[x].fa&&p[x].son[i]!=p[x].hson)
        {
            if(!p[x].bg)p[x].bg=p[x].son[i];
            mm.push_back(p[x].son[i]);
            p[x].en=p[x].son[i];
        }
    int tb=0;
    if(p[x].hson)lscl(p[x].hson,mm);
    for(int i=0;i<mm.size();++i)
    {
        p[mm[i]].dfn=++t;
        jd[t]=mm[i];
    }
    if(mm.size())p[x].en=mm.back();
    for(int i=0;i<mm.size();++i)
        ltcl(mm[i]);
}
void build(int l,int r,int bh)
{
    x[bh].l=l;
    x[bh].r=r;
    if(l==r)return;
    int mid=(l+r)/2;
    build(l,mid,bh*2);
    build(mid+1,r,bh*2+1);
}
void pushdown(int bh)
{
    if(x[bh].l!=x[bh].r&&x[bh].tag)
    {
        x[bh*2].tag=x[bh*2+1].tag=x[bh].tag;
        if(x[bh].tag==1)
        {
            x[bh*2].sum=x[bh*2].r-x[bh*2].l+1;
            x[bh*2+1].sum=x[bh*2+1].r-x[bh*2+1].l+1;
        }
        else
        {
            x[bh*2].sum=0;
            x[bh*2+1].sum=0;
        }
        x[bh].tag=0;
    }
}
void cha(int l,int r,int t,int bh)
{
    if(r==0)return;
    if(l==0)return;
    if(l>r)return;
    pushdown(bh);
    if(l==x[bh].l&&r==x[bh].r)
    {
        x[bh].tag=t;
        if(t==1)
            x[bh].sum=x[bh].r-x[bh].l+1;
        else
            x[bh].sum=0;
        return;
    }
    int mid=(x[bh].l+x[bh].r)/2;
    if(r<=mid)
    {
        cha(l,r,t,bh*2);
        x[bh].sum=x[bh*2].sum+x[bh*2+1].sum;
        return;
    }
    if(l>mid)
    {
        cha(l,r,t,bh*2+1);
        x[bh].sum=x[bh*2].sum+x[bh*2+1].sum;
        return;
    }
    cha(l,mid,t,bh*2);
    cha(mid+1,r,t,bh*2+1);
    x[bh].sum=x[bh*2].sum+x[bh*2+1].sum;
}
int que(int l,int r,int bh)
{
    if(r==0)return 0;
    if(l==0)return 0;
    if(l>r)return 0;
    pushdown(bh);
    if(l==x[bh].l&&r==x[bh].r)
        return x[bh].sum;
    int mid=(x[bh].l+x[bh].r)/2;
    if(r<=mid)
        return que(l,r,bh*2);
    if(l>mid)
        return que(l,r,bh*2+1);
    int ans=0;
    ans+=que(l,mid,bh*2);
    ans+=que(mid+1,r,bh*2+1);
    return ans;
}
void xg(int a,int b)
{
    int a1=a,b1=b;
    while(p[a].top!=p[b].top)
    {
        if(p[p[a].top].dep<p[p[b].top].dep)
            swap(a,b);
        if(p[a].hson)
            cha(p[p[a].hson].dfn,p[p[a].hson].dfn,-1,1);
        cha(p[p[p[a].top].bg].dfn,
        p[p[a].en].dfn,-1,1);
        a=p[p[a].top].fa;
    }
    if(p[a].dep<p[b].dep)
        swap(a,b);
    if(p[a].hson)
    cha(p[p[a].hson].dfn,p[p[a].hson].dfn,-1,1);
    cha(p[p[b].bg].dfn,
    p[p[a].en].dfn
    ,-1,1);
    while(p[a1].top!=p[b1].top)
    {
        if(p[p[a1].top].dep<p[p[b1].top].dep)
            swap(a1,b1);
        if(a1!=p[a1].top)cha(p[p[p[a1].top].hson].dfn,p[a1].dfn,1,1);
        cha(p[p[a1].top].dfn,p[p[a1].top].dfn,1,1);
        a1=p[p[a1].top].fa;
    }
    if(p[a1].dep<p[b1].dep)
        swap(a1,b1);
    if(a1!=b1)
    {
        if(p[b1].top==b1)
            cha(p[p[b1].hson].dfn,p[a1].dfn,1,1);
        else
            cha(p[b1].dfn,p[a1].dfn,1,1);
    }
    cha(p[b].dfn,p[b].dfn,-1,1);
}
int get(int a,int b)
{
    int ans=0;
    while(p[a].top!=p[b].top)
    {
        if(p[p[a].top].dep<p[p[b].top].dep)
            swap(a,b);
        if(a!=p[a].top)ans+=que(p[p[p[a].top].hson].dfn,p[a].dfn,1);
        ans+=que(p[p[a].top].dfn,p[p[a].top].dfn,1);
        a=p[p[a].top].fa;
    }
    if(p[a].dep<p[b].dep)
        swap(a,b);
    if(p[b].top==b)
    {
        ans+=que(p[b].dfn,p[b].dfn,1);
        if(a!=b)ans+=que(p[p[b].hson].dfn,p[a].dfn,1);
    }
    else
        ans+=que(p[b].dfn,p[a].dfn,1);
    return ans;
}
int main()
{
    //freopen("edge2.in","r",stdin);
    //freopen("edge2.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        t=0;
        memset(jd,0,sizeof jd);
        memset(p,0,sizeof p);
        memset(x,0,sizeof x);
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n-1;++i)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            p[u].son.push_back(v);
            p[v].son.push_back(u);
        }
        p[1].dfn=++t;
        jd[t]=1;
        dfs(1,0);
        ltcl(1);
        build(1,n,1);
        for(int i=1;i<=m;++i)
        {
            int opt,a,b;
            scanf("%d%d%d",&opt,&a,&b);
            if(opt==1)
                xg(a,b);
            else
                printf("%d\n",get(a,b));
        }
    }
    return 0;
}