#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define umap unordered_map
#define empb emplace_back
#define mkp make_pair
#define emp emplace
random_device d;
mt19937 rd(d());

const ll MAXN = 1e5 + 5;

ll n, sit[MAXN], rt;
vector<ll> e[MAXN];
vector<ll> oe[MAXN];
pll en[MAXN];
set<array<ll, MAXN> > ans;

ll fac(ll x) {
	ll ret = 1;
	for (ll i = 1; i <= x; ++i) {
		ret *= i;
	}
	return ret;
}
bool gen() {
	for (ll i = n - 1; i >= 1; --i) {
		if (!next_permutation(e[i].begin(), e[i].end())) {
			sort(e[i].begin(), e[i].end());
			if (i == 1) {
				return 0;
			}
		} else {
			break;
		}
	}
	return 1;
}
void srh(ll x, ll pr, umap<ll, bool>& vis, array<ll, MAXN>& p) {
	vis[x] = 1, p[x] = pr;
	for (ll i : e[x]) {
		if (vis[i]) {
			continue;
		}
		srh(i, x, vis, p);
	}
}

void init() {
	for (ll i = 1; i <= n; ++i) {
		e[i].clear();
		oe[i].clear();
	}
}
int mian() {
	ll k;
	cin >> n >> k;
	for (ll i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		oe[u].empb(i);
		oe[v].empb(i);
		en[i] = mkp(u, v);
	}
	ll tgu, tgv;
	cin >> tgu >> tgv;
	for (ll i = 1; i < n; ++i) {
		if (en[i] == mkp(tgu, tgv) || en[i] == mkp(tgv, tgu)) {
			rt = i;
			break;
		}
	}
	for (ll i = 1; i <= n; ++i) {
		for (ll j = 0; j < oe[i].size(); ++j) {
			for (ll k = j + 1; k < oe[i].size(); ++k) {
				e[j].empb(k);
				e[k].empb(j);
			}
		}
		sit[i] = 1;
	}
	do {
		array<ll, MAXN> p;
		umap<ll, bool> vis;
		srh(rt, 0, vis, p);
		ans.emp(p);
	} while (gen());
	cout << ans.size() << endl;
	return 0;
}

int main() {
	freopen("traverse.in", "r", stdin);
	freopen("traverse.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll T;
	ll u;
	cin >> u >> T;
	while (T--) {
		init();
		mian();
	}
	return 0;
}













































