406254: GYM102331 D Determinant

Um_nik has a simple connected undirected graph with the following property:

For any subset $$$A$$$ of $$$k+1$$$ vertices of the graph, there exist two vertices $$$a, b \in A$$$ and some edge $$$e$$$, such that all paths from $$$a$$$ to $$$b$$$ contain edge $$$e$$$.

Please help him find the determinant of the adjacency matrix of his graph modulo $$$998\,244\,353$$$.

The first line contains three integers $$$n$$$, $$$m$$$, $$$k$$$: the number of vertices and edges in the graph and the given parameter ($$$1 \leq n \leq 25\,000$$$, $$$n - 1 \leq m \leq 500\,000$$$, $$$1 \leq k \leq 25$$$).

The next $$$m$$$ lines describe edges of the graph. Each of them contains two integers $$$u$$$ and $$$v$$$: the two vertices connected by an edge ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$).

It is guaranteed that this graph is connected and also for any subset $$$A$$$ of $$$k+1$$$ vertices of the graph, there exist two vertices $$$a, b \in A$$$ and an edge $$$e$$$ such that all paths from $$$a$$$ to $$$b$$$ contain edge $$$e$$$. It is guaranteed that this graph doesn't contain multiple edges.

Print a single integer: the determinant of Um_nik graph's adjacency matrix modulo $$$998\,244\,353$$$.

4 3 1
1 2
2 3
3 4

1

6 6 3
2 3
5 6
2 5
1 2
3 4
6 2

998244352

10 15 10
1 8
1 7
6 7
2 8
6 9
1 2
4 9
4 10
4 6
5 6
3 8
9 10
8 10
3 5
2 7

35