RT，TLE on #19#20，88 pts

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

const int N = 1e5 + 5, K = 25, MOD = 998244353;
int T, n, m, k, du[N], ans, c[N][K];
int flag[N];	//0-待定,1-留,2-选 
struct Archive{
	int klst, flaglst, dulst;
	vector <int> addlst;
};
set <int> e[N];
vector <pair <int, int> > v;

inline Archive change(int x, int goal)
{
	Archive res;
	res.flaglst = flag[x], res.dulst = du[x], res.klst = k;
	flag[x] = goal;
	if(goal == 2)
	{
		du[x] = 0, k--;
		for(set<int>::iterator it = e[x].begin();it != e[x].end();it++)
			if(flag[*it] == 0 && du[*it])
				du[*it]--, res.addlst.push_back(*it);
	}
	return res;
}

inline void back(int x, Archive arc)
{
	flag[x] = arc.flaglst, du[x] = arc.dulst, k = arc.klst;
	for(register int i = 0;i < arc.addlst.size();i++)	du[arc.addlst[i]]++;
}

inline void dfs(int x)
{
	//printf("%d %d %d %d\n", x, v[x].first, v[x].second, k);
	//for(int i = 1;i <= n;i++)	printf("%d ", flag[i]);
	//puts("");
	if(k < 0)
		return ;
	if(x == v.size())
	{
		register int tmp = 0;
		for(register int i = 1;i <= n;i++)
			if(flag[i] == 0)	tmp++;
		(ans += c[tmp][k]) %= MOD;
		//printf("%d %d\n", tmp, ans);
		return ;
	}
	if(flag[v[x].first] == 2 || flag[v[x].second] == 2)
	{
		dfs(x + 1);
		return ;
	}
	if(flag[v[x].first] == 0)
	{
		if(flag[v[x].second] == 1)
		{
			Archive arc = change(v[x].first, 2);
			dfs(x + 1);
			back(v[x].first, arc);
		}
		else if(flag[v[x].second] == 0)
		{
			Archive arca = change(v[x].first, 2), arcb = change(v[x].second, 2);
			dfs(x + 1), k += 2;
			change(v[x].first, 1), change(v[x].second, 2);
			dfs(x + 1), k += 1;
			change(v[x].first, 2), change(v[x].second, 1);
			dfs(x + 1), k += 1;
			back(v[x].second, arcb);
			back(v[x].first, arca);
		}
	}
	if(flag[v[x].first] == 1)
	{
		if(flag[v[x].second] == 0)
		{
			Archive arc = change(v[x].second, 2);
			dfs(x + 1);
			back(v[x].second, arc);
		}
	}
	return ;
}

inline void solve()
{
	v.clear(), ans = 0;
	scanf("%d %d %d", &n, &m, &k);
	for(register int i = 1;i <= n;i++)	du[i] = flag[i] = 0, e[i].clear();
	for(register int i = 1, u, v;i <= m;i++)
	{
		scanf("%d %d", &u, &v);
		e[u].insert(v);
		e[v].insert(u);
	}
	for(register int i = 1;i <= n;i++)	du[i] = e[i].size();
	while(k)
	{
		int mx = 0;
		for(register int i = 1;i <= n;i++)	if(du[i] > du[mx])	mx = i;
		if(du[mx] <= k)	break;
		change(mx, 2);
		//printf("%d\n", k);
	}
	if(k < 0)
	{
		puts("0");
		return ;
	}
	for(register int i = 1;i <= n;i++)
	{
		for(set<int>::iterator it = e[i].begin();it != e[i].end();it++)
		{
			if(*it <= i || flag[i] == 2 || flag[*it] == 2)
				continue;
			v.push_back(make_pair(i, *it));
			if(v.size() > k * k)
			{
				puts("0");
				return ;
			}
		}
	}
	//printf("edge:%d\n", v.size());
	dfs(0);
	printf("%d\n", ans);
	return ;
}

signed main()
{
	for(register int i = 0;i <= 100000;i++)	c[i][0] = 1;
	for(register int i = 1;i <= 100000;i++)
		for(register int j = 1;j <= min(i, 18);j++) c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
	scanf("%d", &T);
	while(T--)	solve();
	return 0;
}