Determinant
시간 제한5초메모리 제한512 MB
임의의 k+1개 정점 중 두 정점이 단 하나의 단절 간선으로만 연결되는 연결 그래프가 주어질 때, 인접 행렬의 행렬식을 998244353으로 나눈 나머지를 구한다.
문제
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.
힌트
