#P18419. Sets May Be Good

Sets May Be Good

Sets May Be Good

给定一个有 nn 个顶点的无向图 GG。若某个顶点子集内部的边数为偶数,就称这个子集是好的。这里“内部的边”指两个端点都属于该子集的边。

求好子集的数量,对质数 998244353998244353 取模。空集也属于顶点子集,其内部有零条边。

输入格式

第一行两个整数 n,mn,m(1≤n≤10001\le n\le1000,0≤m≤n(n−1)/20\le m\le n(n-1)/2),分别表示顶点数、边数。

接下来 mm 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n),表示连接顶点 u,vu,v 的一条边。

保证没有自环和重边。

输出格式

输出一个整数,表示好子集数量模 998244353998244353 的结果。

原样例

样例 1

5 5
1 2
2 3
3 4
4 5
1 5
16

样例 2

3 0
8

样例 3

2 1
1 2
3

说明

第二个样例中,所有子集都是好的。第三个样例中,唯一不好的子集是 {1,2}\{1,2\}。