#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005

int c, t, n, k;

namespace sol1{
	vector<int> e[MAXN];
	struct Edge{int u, v;}egs[MAXN];
	set<vector<pair<int, int>>> st; bitset<MAXN> vis; vector<pair<int, int>> nw;
	void dfs(int x){
		vis[x] = 1;
		if (vis.count() == n-1){
			auto p(nw); sort(p.begin(), p.end()); st.insert(p); vis[x] = 0; return;
		}
		for (auto i: e[x]) if (!vis[i]){
			nw.push_back({min(x, i), max(x, i)}); dfs(i); nw.pop_back();
		}
		vis[x] = 0;
	}
	void sol(){
		for (int i(1); i<n; ++i) cin >> egs[i].u >> egs[i].v;
		for (int i(1); i<n; ++i) for (int j(1); j<n; ++j){
			if (egs[i].u == egs[j].v || egs[i].v == egs[j].v || egs[i].v == egs[j].u || egs[i].u == egs[j].u){
				e[i].push_back(j);
			}
		}
		int rt; cin >> rt; dfs(rt); cout << st.size() << '\n';
	}
}

signed main(){
	freopen("traverse.in", "r", stdin); freopen("traverse.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> c >> t;
	for (; t; --t){
		cin >> n >> k; if (n <= 5 && k == 1) sol1::sol(); else cout << "1\n";
	}
	
	return 0;
}

