{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/zn5t5x28.png)"},{"iden":"statement","content":"小 S 有一个伟大的梦想：证明 $\\text{P}=\\text{NP}$。\n\n有一天，他得知一般图最大独立集是 NPC 问题后，决定解决他。\n\n当然小 S 太菜了，解决不了，于是求助于你：\n\n> 给出一个含有 $n$ 个顶点，$m$ 条边的无向图 $G$，求 $G$ 中大小恰好为 $n-k$ 的独立集的数量。由于答案可能很大，请将其对 $998~244~353$ 取模。\n\n小 S 不喜欢多测，因为他在 NOIp 中因为多测挂分，所以本题包含多组测试数据。"},{"iden":"input","content":"**本题包含多组测试数据。**\n\n第一行一个正整数 $T$，表示测试数据组数。\n\n对于每组测试数据，第一行三个正整数 $n,m,k$。\n\n接下来 $m$ 行，每行两个正整数 $u,v$ 表示一条边。\n\n保证图中不存在自环，但**可能存在重边**。"},{"iden":"output","content":"对于每组测试数据，输出一行一个正整数，表示符合要求的独立集数量。答案对 $998~244~353$ 取模。"},{"iden":"note","content":"**【样例解释】**\n\n对于第 $1,2$ 组测试数据，图是完全图，容易发现，完全图的最大独立集为 $1$，并且每一个顶点都单独构成一个独立集。因此第 $1$ 组测试数据的答案为 $0$，第 $2$ 组测试数据的答案为 $4$。\n\n对于第 $3$ 组测试数据，该组数据中给出的无向图如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/abt8ho3b.png)\n\n其中，所有大小为 $3$ 的独立集为：\n\n+ $\\{2,4,8\\}$；\n+ $\\{2,3,7\\}$；\n+ $\\{3,4,6\\}$；\n+ $\\{2,4,6\\}$；\n+ $\\{1,4,6\\}$；\n+ $\\{2,3,6\\}$；\n+ $\\{1,4,5\\}$；\n+ $\\{2,3,4\\}$。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n![数据范围](https://cdn.luogu.com.cn/upload/image_hosting/p3jwdqp3.png)\n\n对于 $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$。\n\n并且对于每个测试点保证：\n\n设 $K=\\max k$，即该测试点中所有 $k$ 的最大值，\n\n+ 若 $K\\ge 17$，则 $T=1$；\n+ 若 $K\\ge 15$，则 $T\\le 3$；\n+ 若 $K\\ge 10$，则 $T\\le 5$；\n+ 若 $K\\ge 5$，则 $T\\le 300$。\n"}],"translated_statement":null,"sample_group":[["3\n4 6 1\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n4 6 3\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n8 13 5\n1 2\n7 8\n1 3 \n2 5\n3 8\n6 8\n4 7\n5 6\n5 7\n5 8\n6 7\n1 8\n3 5","0\n4\n8"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}