P9036 "KDOI-04" Challenge NPC III


Xiao S has a great dream: to prove that $\text{P}=\text{NP}$. One day, after learning that the maximum independent set problem on general graphs is an NPC problem, he decided to solve it. Of course, Xiao S is too weak to solve it, so he asks you for help: > Given an undirected graph $G$ with $n$ vertices and $m$ edges, find the number of independent sets in $G$ whose size is exactly $n-k$. Since the answer may be very large, output it modulo $998~244~353$. Xiao S does not like multiple test cases, because he lost points in NOIp due to multiple test cases, so this problem contains multiple groups of testdata.

**This problem contains multiple groups of testdata.** The first line contains a positive integer $T$, the number of test cases. For each test case, the first line contains three positive integers $n,m,k$. The next $m$ lines each contain two positive integers $u,v$, representing an edge. It is guaranteed that there are no self-loops in the graph, but **there may be multiple edges**.

For each test case, output one line with one positive integer, the number of independent sets that meet the requirement, modulo $998~244~353$.

**[Sample Explanation]** For test cases $1$ and $2$, the graph is a complete graph. It is easy to see that the maximum independent set of a complete graph has size $1$, and each single vertex forms an independent set. Therefore, the answer for test case $1$ is $0$, and the answer for test case $2$ is $4$. For test case $3$, the undirected graph is as follows:  All independent sets of size $3$ are: + $\{2,4,8\}$； + $\{2,3,7\}$； + $\{3,4,6\}$； + $\{2,4,6\}$； + $\{1,4,6\}$； + $\{2,3,6\}$； + $\{1,4,5\}$； + $\{2,3,4\}$。 **[Constraints]** **This problem uses bundled tests.**  For $100\%$ of the data, it is guaranteed that $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$. Also, for each test point: Let $K=\max k$, i.e. the maximum value of $k$ among all test cases in this test point. + If $K\ge 17$, then $T=1$； + If $K\ge 15$, then $T\le 3$； + If $K\ge 10$, then $T\le 5$； + If $K\ge 5$, then $T\le 300$。 Translated by ChatGPT 5