Independent Sets of Fixed Size

Little S has a grand dream: to prove that \(\text{P}=\text{NP}\). One day, upon learning that the Maximum Independent Set problem in a general graph is NP‐complete, he decided to tackle it. However, being not so skilled, he eventually asks for your help:

Given an undirected graph \(G\) with \(n\) vertices and \(m\) edges, count the number of independent sets in \(G\) whose size is exactly \(n-k\). Since the answer may be large, output it modulo \(998\,244\,353\).

Note that an independent set is a set of vertices in which no two vertices share an edge. This problem contains multiple test cases.

inputFormat

The first line contains an integer \(T\) (\(1 \le T\le \ldots\)), the number of test cases.

For each test case, the first line contains three integers \(n\), \(m\), and \(k\), where \(n\) is the number of vertices, \(m\) is the number of edges, and you are required to count independent sets of size exactly \(n-k\).

The next \(m\) lines each contain two integers \(u\) and \(v\) (1-indexed), indicating an undirected edge between vertices \(u\) and \(v\).

outputFormat

For each test case, print a single line containing the number of independent sets of size \(n-k\) in the given graph, modulo \(998\,244\,353\).

sample

3
3 2 1
1 2
2 3

1