#P18419. Sets May Be Good
Sets May Be Good
Sets May Be Good
给定一个有 个顶点的无向图 。若某个顶点子集内部的边数为偶数,就称这个子集是好的。这里“内部的边”指两个端点都属于该子集的边。
求好子集的数量,对质数 取模。空集也属于顶点子集,其内部有零条边。
输入格式
第一行两个整数 (,),分别表示顶点数、边数。
接下来 行,每行两个整数 (),表示连接顶点 的一条边。
保证没有自环和重边。
输出格式
输出一个整数,表示好子集数量模 的结果。
原样例
样例 1
5 5
1 2
2 3
3 4
4 5
1 5
16
样例 2
3 0
8
样例 3
2 1
1 2
3
说明
第二个样例中,所有子集都是好的。第三个样例中,唯一不好的子集是 。