#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define int long long
const int mod = 1e9+7;
int n,m,i,j,ans,a,b,c,y,t,k,h[N],L[N],R[N],e[N],flag[N],pre[N],aa[N],bb[N];
int mp[1005][1005],S[N];
struct AB{
	int a,b,n;
}d[N<<1];
void cun(int a,int b){
	d[++k].a=a,d[k].b=b;
	d[k].n=h[a],h[a]=k;
}
/*
1 1
4 1
1 2
2 3
2 4
1
*/
void dfs(int k,int s,int cnt){
	if(cnt==n-2){
		if(!S[s]) S[s]=1,ans++;
		return;
	}
	for(int i=1;i<n;i++){
		if(!mp[k][i]) continue;
		if(s&(1<<i)) continue;
		dfs(i,s^(1<<i),cnt+1);
	}
}
signed main(){
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	scanf("%lld%lld",&c,&t);
	while(t--){
		memset(S,0,sizeof(S));
		memset(h,0,sizeof(h));
		scanf("%lld%lld",&n,&m),k=0;
		for(i=1;i<n;i++){
			scanf("%lld%lld",&a,&b);
			L[i]=a,R[i]=b,flag[i]=0;
			cun(a,b),cun(b,a);
		}
		if(c==18){
			puts("1");
			continue;
		}
		for(i=1;i<n;i++){
			for(j=1;j<n;j++) mp[i][j]=0;
		}
		for(i=1;i<n;i++){
			for(j=1;j<n;j++){
				if(i==j) continue;
				if(L[i]==L[j] || L[i]==R[j] || R[i]==L[j] || R[i]==R[j]) mp[i][j]=1;
			}
		}
		for(i=1;i<=m;i++) scanf("%lld",&e[i]);
		ans=0;
		for(i=1;i<=m;i++){
			dfs(i,(1<<i),1);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
