$O(2^kk^2)$，是写假了吗

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define pb push_back
#define se second
#define ll long long
namespace Maths {
	ll mod = 998244353;
	ll fac[1000010], inv[1000010];
	ll C(int n, int m) {
		if (m > n) return 0;
		if (n < 0 || m < 0) return 0;
		return fac[n] * inv[n - m] % mod * inv[m] % mod;
	}
	ll P(int x, int y) {
		if (!y) return 1;
		ll s = P(x, y / 2);
		if (y & 1) return s * s % mod * x % mod; else return s * s % mod;
	}
	void init() {
		fac[0] = 1;
		for (int i = 1; i <= 1e6; i++) fac[i] = fac[i - 1] * i % mod;
		inv[1] = 1;
		for (int i = 2; i <= 1e6; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		inv[0] = 1;
		for (int i = 1; i <= 1e6; i++) inv[i] = inv[i - 1] * inv[i] % mod;
	}
}
using namespace Maths;

int n, m, k, ind[1000010], sel[1000010], du[1000010];
map<int, map<int, int> > p;
vector<int> g[1000010], e[1000010], can;
int chk() {
	int m = 0;
	for (int i = 0; i < can.size(); i++) {
		int u = can[i];
		if (sel[u] == 1) continue;
//		cout << u << " is good\n";
		du[u] = 0;
		for (int j = 0; j < e[u].size(); j++) {
			int v = e[u][j];
			if (sel[v] != 1) {
				m++; du[u]++;
//				cout << u << " -> " << v << "\n";
			}
		}
	}
	return m / 2;
}
ll dfs(int dep) {
	if (!m) {
		int cnt = 0;
		for (int i = 0; i < can.size(); i++) {
			int u = can[i];
			if (sel[u] == 0) cnt++; 
		}
		return C(cnt, k);
	}
	if (k <= 0) return 0;
	int mx = 0, mxu = 0;
	for (int i = 0; i < can.size(); i++) {
		int u = can[i];
		if (sel[u] != 0) continue;
		if (du[u] > mx) mx = du[u], mxu = u;
	}
	if (!mxu) return 0;
//	for (int i = 0; i < can.size(); i++) {
		int u = mxu;
//		if (sel[u] != 0) continue;
		k--;
		sel[u] = 1;
		m = chk();
		ll ans = dfs(dep + 1);
		k++;
		int QwQk = k;
		sel[u] = -1;
		bool flag = 1;
		stack<int> st; 
		while (st.size()) exit(1);
		for (int j = 0; j < e[u].size(); j++) {
			int v = e[u][j];
			if (sel[v] == -1) flag = 0;
			if (sel[v] == 0) {
				sel[v] = 1; k--; st.push(v);
			}
		}
		m = chk();
		if (flag) ans += dfs(dep + 1);
		k = QwQk;
		sel[u] = 0;
		while (st.size()) {
			sel[st.top()] = 0; st.pop(); 
		}
		m = chk();
		if (ans >= mod) ans -= mod;
		return ans;
//	}
	return 0;
}
int read() {
	int a = 0, b = 1;
	char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') b = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		a = a * 10 + c - '0'; c = getchar();
	}
	return a * b;
}
signed main() {
	init();
	int T;
	cin >> T;
	while (T--) {
		n = read(), m = read(), k = read();
		for (int i = 1; i <= n; i++) ind[i] = sel[i] = 0;
		vector<int>().swap(can);
		for (int i = 1; i <= n; i++) p[i].clear();
		for (int i = 1; i <= n; i++) vector<int>().swap(e[i]), vector<int>().swap(g[i]);
		while (m--) {
			int u, v;
			u = read(), v = read(); 
			if (p[u][v]) continue;
			ind[u]++, ind[v]++;
			g[u].pb(v), g[v].pb(u);
			p[u][v] = p[v][u] = true;
		}
		int OrZ = k;
		for (int i = 1; i <= n; i++) {
			if (ind[i] > k) {
				k--;
				sel[i] = 1;
				ind[i] = 0; 
				for (int j = 0; j < g[i].size(); j++) ind[g[i][j]]--;
			}
			if (k < 0) break;
		}
		if (k < 0) {
			printf("0\n"); continue;
		}
//		if (k == 0) {
//			cout << "1\n"; continue;
//		} 
		for (int i = 1; i <= n; i++) {
			if (sel[i]) continue;
			can.pb(i);
			for (int j = 0; j < g[i].size(); j++) {
				int v = g[i][j];
				if (!sel[v]) {
					e[i].pb(v); 
				}
			}
		}
		m = chk();
		if (m > k * OrZ) {
		    printf("0\n"); continue;
		}
		printf("%lld\n", dfs(1));
	}
	return 0;
}