H. Alexandria Library

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define eb emplace_back
#define mkp make_pair

const ll MAXN=3e5+5;

ll n,Q,x,y;
vector<ll> G[MAXN];
ll dep[MAXN],sz[MAXN],fa[21][MAXN];

void dfs(ll now,ll pa){
    sz[now]=1;
    fa[0][now]=pa;
    for(auto it:G[now]){
        if(it!=pa){
            dep[it]=dep[now]+1;
            dfs(it,now);
            sz[now]+=sz[it];
        }
    }
}

void bulid_lca(ll root){
    dep[root]=1;
    dfs(root,root);
    for(ll i=1;i<log2(n);i++){
        for(ll j=1;j<=n;j++){
            fa[i][j]=fa[i-1][fa[i-1][j]];
        }
    }
}

ll lca(ll a,ll b){
    if(dep[a]>dep[b]) swap(a,b);
    ll gap=dep[b]-dep[a];
    for(ll i=0;i<log2(n);i++){
        if(gap>>i&1) b=fa[i][b];
    }
    if(a==b) return a;
    for(ll i=20;i>=0;i--){
        if(fa[i][a]!=fa[i][b]){
            a=fa[i][a];
            b=fa[i][b];
        }
    }
    return fa[0][a];
}

void init(){
    cin>>n>>Q;
    for(ll j=1;j<=n;j++){
        G[j].clear();
        for(ll i=0;i<21;i++){
            fa[i][j]=1;
        }
    }
    for(ll i=0;i<n-1;i++){
        cin>>x>>y;
        G[x].eb(y);
        G[y].eb(x);
    }
    dfs(1,1);
    bulid_lca(1);
}

void solve(){
    while(Q--){
        cin>>x>>y;
        ll ans=lca(x,y);
        if((dep[x]+dep[y]-2*dep[ans])%2==1){
            cout<<"0\n";
            continue;
        }
        if(x==y){
            cout<<n<<'\n';
            continue;
        }
        if(dep[x]>dep[y]) swap(x,y);
        ll gap=(dep[x]+dep[y]-2*dep[ans])/2;
        ll mid=y;
        for(ll i=20;i>=0;i--){
            if(gap>>i&1) mid=fa[i][mid];
        }
        if(ans==mid){
            gap--;
            for(ll i=20;i>=0;i--){
                if(gap>>i&1){
                    y=fa[i][y];
                    x=fa[i][x];
                }
            }
            cout<<n-sz[y]-sz[x]<<'\n';
        }
        else{
            gap--;
            for(ll i=20;i>=0;i--){
                if(gap>>i&1) y=fa[i][y];
            }
            cout<<sz[mid]-sz[y]<<'\n';
        }
    }
}

signed main(){
    fastio
    freopen("library.in","r",stdin);
    ll T;
    cin>>T;
    while(T--){
        init();
        solve();
    }
    return 0;
}