ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Petrozavodsk Summer 2018. t.me/umnik_team Contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Determinant of a Graph

Time limit: 2.0 second
Memory limit: 128 MB
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.

Input

The first line contains two integers n and m: the number of vertices and edges in the graph (1 ≤ n ≤ 2 · 105, n − 1 ≤ mn + 50).
The next m lines describe edges of the graph. Each of them contains two integers u and v (1 ≤ u, vn): 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.

Output

Print a single integer: the determinant of the graph’s adjacency matrix modulo 998 244 353.

Samples

inputoutput
4 3
1 2
2 3
3 4
1
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
4
1 0
0
2 1
2 1
998244352
Problem Author: Alexey Danilyuk
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest
To submit the solution for this problem go to the Problem set: 2127. Determinant of a Graph