시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 4 4 4 100.000%

문제

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 ∈ 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 ≤ n ≤ 25 000, n − 1 ≤ m ≤ 500 000, 1 ≤ k ≤ 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 ≤ u, v ≤ n, u ≠ 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 ∈ 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.

예제 입력 1

4 3 1
1 2
2 3
3 4

예제 출력 1

1

예제 입력 2

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

예제 출력 2

998244352

예제 입력 3

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

예제 출력 3

35

힌트

출처

Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 2 D번

  • 문제를 만든 사람: 300iq