Background

Problem Description

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.

Input Format

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.

Output Format

For each test case, output one line with one positive integer, the number of independent sets that meet the requirement, modulo $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

Hint

[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