#include<cstdio>
#include<vector>
#include<set>
#include<utility>
#include<map>
using namespace std;
const int N=1e5+5;
typedef long long ll;
template<typename T>
void read(T &x){
    x=0;
    char ch;
    while((ch=getchar()))
        if('0'<=ch&&ch<='9') break;
    while('0'<=ch&&ch<='9'){
        x = x*10+ch-'0';
        ch=getchar();
    }
}
int a,b;
struct graph{
    struct edge{
        int v,nt;
    }e[N<<1];
    int tot,hd[N];
    void add(int u,int v){e[++tot]={v,hd[u]},hd[u]=tot;}
    void uadd(int u,int v){add(u,v),add(v,u);}
}g,tr;
void create(int x,int f){
    vector<int> vc;
    vc.clear();
    for(int i=g.hd[x];i;i=g.e[i].nt){
        int v=g.e[i].v;
        if(v==f) continue;
        if(x!=1) tr.uadd(x,v);
        vc.push_back(v);
        create(v,x);
    }
    for(auto e1:vc)
        for(auto e2:vc)
            if(e1!=e2) tr.uadd(e1,e2);
}
#define pii pair<int,int>
map<set<pii>,bool> mp;
bool vis[N];
ll ans;
int n,k;
void dfs(int x,int f,int cnt,set<pii> gra){
    if(cnt>k){
        if(!mp[gra]) ans++,mp[gra]=1;
        return;
    }
    for(int i=tr.hd[x];i;i=tr.e[i].nt){
        int v = tr.e[i].v;
        if(vis[v]) continue;
        vis[v]=1;
        gra.insert({min(x,v),max(x,v)});
        dfs(v,x,cnt+1,gra);
        vis[v]=0;
        gra.erase({min(x,v),max(x,v)});
    }
}
int C,T;
int main(){
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
    read(C),read(T);
    while(T--){
        read(n),read(k);
        int u,v;
        g.tot=0;
        for(int i=1;i<n;i++)
            read(u),read(v),g.uadd(u,v);
        create(1,0);
        for(int i=2;i<=n;i++){
            vis[i]=1,dfs(i,0,1,{}),vis[i]=0;
        }
        printf("%lld\n",ans);
    }
	return 0;
}
