「KDOI-04」挑战 NPC Ⅲ


小 S 有一个伟大的梦想：证明 $\text{P}=\text{NP}$。 有一天，他得知一般图最大独立集是 NPC 问题后，决定解决他。 当然小 S 太菜了，解决不了，于是求助于你： > 给出一个含有 $n$ 个顶点，$m$ 条边的无向图 $G$，求 $G$ 中大小恰好为 $n-k$ 的独立集的数量。由于答案可能很大，请将其对 $998~244~353$ 取模。 小 S 不喜欢多测，因为他在 NOIp 中因为多测挂分，所以本题包含多组测试数据。

**本题包含多组测试数据。** 第一行一个正整数 $T$，表示测试数据组数。 对于每组测试数据，第一行三个正整数 $n,m,k$。 接下来 $m$ 行，每行两个正整数 $u,v$ 表示一条边。 保证图中不存在自环，但**可能存在重边**。

对于每组测试数据，输出一行一个正整数，表示符合要求的独立集数量。答案对 $998~244~353$ 取模。

3
4 6 1
1 2
1 3
1 4
2 3
2 4
3 4
4 6 3
1 2
1 3
1 4
2 3
2 4
3 4
8 13 5
1 2
7 8
1 3 
2 5
3 8
6 8
4 7
5 6
5 7
5 8
6 7
1 8
3 5

0
4
8

**【样例解释】** 对于第 $1,2$ 组测试数据，图是完全图，容易发现，完全图的最大独立集为 $1$，并且每一个顶点都单独构成一个独立集。因此第 $1$ 组测试数据的答案为 $0$，第 $2$ 组测试数据的答案为 $4$。 对于第 $3$ 组测试数据，该组数据中给出的无向图如下：  其中，所有大小为 $3$ 的独立集为： + $\{2,4,8\}$； + $\{2,3,7\}$； + $\{3,4,6\}$； + $\{2,4,6\}$； + $\{1,4,6\}$； + $\{2,3,6\}$； + $\{1,4,5\}$； + $\{2,3,4\}$。 **【数据范围】** **本题采用捆绑测试。**  对于 $100\%$ 的数据，保证 $1\leq n\leq10^5$，$0\le m\le 10^5$，$0\leq k\leq \min(n-1,18)$，$1\leq T\leq 10^{4}$，$\sum n,\sum m\leq10^6$。 并且对于每个测试点保证： 设 $K=\max k$，即该测试点中所有 $k$ 的最大值， + 若 $K\ge 17$，则 $T=1$； + 若 $K\ge 15$，则 $T\le 3$； + 若 $K\ge 10$，则 $T\le 5$； + 若 $K\ge 5$，则 $T\le 300$。