# include<bits/stdc++.h>
# define int long long
using namespace std;

struct node{
	int x,y;
}arr[105];
int c,T,n,x,y,bian[10][10],vis[105][105],vis2[105],vis3[1<<19],cnt,k,st,ans;
vector<int> v[10];
void dfs(int cur,int num) {
	if (num == n-1) {
	//	cout << "check!" << endl;
		int tmp = 0;
		for (int i = 1;i < n;i++) {
			for (int j = i+1;j < n;j++) {
				//cout << i << ' ' << j << ' ' << vis[i][j] << endl;
				if (vis[i][j]) tmp = tmp*2+1;
				else tmp = tmp*2;
			}
		}
		if (!vis3[tmp]) ans++;
		vis3[tmp] = 1;
		//cout << endl << endl;
		return;
	}
	int sz = v[cur].size();
	for (int i = 0;i < sz;i++) {
		int nx = v[cur][i];
		//cout << "dfs:" << cur << ' ' << nx << ' ' << num << endl;
		if (vis2[nx]) continue;
		vis[cur][nx] = vis[nx][cur] = 1,vis2[nx] = 1;
		dfs(nx,num+1);
		vis[cur][nx] = vis[nx][cur] = 0,vis2[nx] = 0;
	}
}
signed main() {
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	//freopen("out.txt","w",stdout);
	cin >> c >> T;
	while (T--) {
		cin >> n >> k;
		cnt = 0;
		for (int i = 1;i <= n;i++) v[i].clear();
		for (int i = 1;i < n;i++) {
			cin >> x >> y;
			arr[++cnt] = {x,y};
		}
		for (int i = 1;i < n;i++) {
			for (int j = i+1;j < n;j++) {
				if (arr[i].x == arr[j].x || arr[i].x==arr[j].y || arr[i].y==arr[j].x||arr[i].y==arr[j].y) {
					v[i].push_back(j);
					v[j].push_back(i);
				}
			}
		}
		cin >>st;
		memset(vis,0,sizeof(vis));
		memset(vis2,0,sizeof(vis2));
		memset(vis3,0,sizeof(vis3));
		ans = 0;
		vis2[st] = 1;
		dfs(st,1);
		cout << ans << endl;
	}
	
	return 0;
}
/*
1 5
4 1
1 2
2 3
2 4
1
4 1
1 2
2 3
2 4
1
4 1
1 2
2 3
2 4
1
4 1
1 2
2 3
2 4
1
4 1
1 2
2 3
2 4
1
*/
