#include <cstdio>
#define int long long
const int mod = 1e9 + 7;

int c, n, T, l[10], r[10], k, m, ans, vis[10], sum;

void dfs(int i, int fa) {
	if (sum == n - 1) ans++;
	for (int j = 1; j < n; j++)
		if (!vis[j] && (l[fa] == l[j] || l[fa] == r[j] || r[fa] == l[j] || r[fa] == r[j]) && j > i)
			vis[j] = 1, sum++, dfs(j, j), dfs(j, fa), vis[j] = 0, sum--;
	return;
}

signed main(void) {
	freopen("traverse.in", "r", stdin);
	freopen("traverse.out", "w", stdout);
	scanf("%lld %lld", &c, &T);
	while (T--) {
	scanf("%lld %lld", &n, &k);
	for (int i = 1; i < n; i++)
		scanf("%lld %lld", l + i, r + i);
	scanf("%lld", &m);
	ans = 0;
	vis[m] = sum = 1;
	dfs(m, m);
	vis[m] = 0;
	printf("%lld\n", ans >> 1);
	}
	
	return 0;
}
