시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 2 | 2 | 2 | 100.000% |
Consider an undirected graph $G$ with $n$ vertices. A subset of its vertices is good if the total number of edges between them (edges such that both their ends are in this subset) is even. How many good sets are there? Since this number may be large, output it modulo prime number $998\,244\,353$.
The first line contains two integers $n$ and $m$ ($1 \le n \le 1000$, $0 \le m \le \frac{n(n-1)}{2}$): the number of vertices and edges in the graph, respectively.
Each of the following $m$ lines contains two numbers $u$ and $v$ ($1 \le u, v \le n$): the vertices connected by an edge.
The graph is guaranteed to contain no loops or multiple edges.
Output the number of good sets modulo $998\,244\,353$.
5 5 1 2 2 3 3 4 4 5 1 5
16
3 0
8
2 1 1 2
3
In the second example, all sets are good. In the third example, the only non-good set is $\{1, 2\}$.