#include <bits/stdc++.h>

using namespace std;

const int N = 10;

int n, k, s, cnt;
vector<pair<int, int>> e1[N], e2[N];
bool vis[N];

inline int popcnt(int x) {
	int res = 0;
	for (; x; x >>= 1) res += x & 1;
	return res;
}

void dfs(int u, int fa, int S) {
	vis[u] = 1;
	for (auto eg : e2[u]) {
		int v = eg.first, id = eg.second;
		if (v == fa || !((S >> id) & 1)) continue;
		dfs(v, u, S);
	}
}

bool check(int S) {
	memset(vis, 0, sizeof(vis));
	dfs(s, 0, S);
	for (int i = 1; i < n; i++)
		if (!vis[i]) return 0;
	return 1;
}

void solve() {
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		e1[u].emplace_back(v, i);
		e1[v].emplace_back(u, i);
	}
	cin >> s;

	for (int u = 1; u <= n; u++) {
		for (auto v1 : e1[u]) {
			for (auto v2 : e1[u]) {
				if (v1 >= v2) continue;
				e2[v1.second].emplace_back(v2.second, cnt);
				e2[v2.second].emplace_back(v1.second, cnt++);
			}
		}
	}
	
//	for (int i = 1; i < n; i++) {
//		printf("i:%d ", i);
//		for (auto j : e2[i]) {
//			printf("%d ", j);
//		}
//		puts("");
//	}
	int ans = 0;
	for (int S = 0; S < (1 << cnt); S++) {
		if (popcnt(S) != n - 2) continue;
		if (check(S)) ans++;
	}
	
	cout << ans;
}

int main() {
	freopen("traverse.in", "r", stdin);
	freopen("traverse.out", "w", stdout);
	
	int c, t;
	cin >> c >> t;
	while (t--) solve();
	
	return 0;
} 
