Sets May Be Good

시간 제한2초메모리 제한1024 MB

요약

무방향 그래프에서 내부에 포함된 간선 수가 짝수인 정점 부분집합의 개수를 998244353으로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 수학, 그래프, 비트 연산, 조합론
정답자: 아직 제출이 없습니다

문제

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$ .

힌트

In the second example, all sets are good. In the third example, the only non-good set is $\\{1, 2\\}$ .

예제3

예제 1
입력
```
5 5
1 2
2 3
3 4
4 5
1 5
```
예상 출력
```
16
```
예제 2
입력
```
3 0
```
예상 출력
```
8
```
예제 3
입력
```
2 1
1 2
```
예상 출력
```
3
```