시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2 2 2 100.000%

문제

Consider a connected undirected graph in which the difference between the number of edges and the number of vertices is at most $50$. Please find the determinant of its adjacency matrix modulo $998\,244\,353$.

입력

The first line contains two integers $n$ and $m$: the number of vertices and edges in the graph ($1 \le n \le 2 \cdot 10^{5}$, $n - 1 \le m \le n + 50$).

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

It is guaranteed that the graph does not contain self-loops and multiple edges. It is guaranteed that the graph is connected.

출력

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

예제 입력 1

4 3
1 2
2 3
3 4

예제 출력 1

1

예제 입력 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

예제 출력 2

4

예제 입력 3

1 0

예제 출력 3

0

예제 입력 4

2 1
2 1

예제 출력 4

998244352