# include <cstdio>
# define int long long
# define mod 1000000007
using namespace std;
int T,n,k,d[100007],taskid,a[100007],b[100007],s[100007],sum,bz[72];
int read()
{
	char ch=' ';
	int ans=0;
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
	return ans;
}
void dg(int x)
{
	if(x>=n)
	{
		for(int i=1;i<n-1;i++)
		{
			if(a[d[i]]!=a[d[i+1]])
			if(a[d[i]]!=b[d[i+1]])
			if(b[d[i]]!=a[d[i+1]])
			if(b[d[i]]!=b[d[i+1]])
				return;
		}
		sum++;
		return;
	}
	for(int i=1;i<n;i++)
	{
		if(bz[i]==0)
		{
			bz[i]=1,d[x]=i;
			dg(x+1);
			bz[i]=0;
		}
	}
}
signed main()
{
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	scanf("%lld%lld",&taskid,&T);
	for(int happy=1;happy<=T;happy++)
	{
		scanf("%lld%lld",&n,&k);
		for(int i=1;i<n;i++)
			a[i]=read(),b[i]=read();
		for(int i=1;i<=k;i++) s[i]=read();
		if(taskid==18)
		{
			printf("1\n");
			continue;
		}
		if(taskid<=3)
		{
			sum=0;
			d[1]=s[1];
			bz[s[1]]=1;
			dg(2);
			bz[s[1]]=0;
			printf("%lld\n",sum);
			continue;
		}
	}
}
