Migrated from Lutece 1332 沈宝宝与二分图

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

沈宝宝开始学习二分图啦

现在沈宝宝有了一个二分图，沈宝宝想知道有多少种方法选择一个点集$D$

使得整个二分图中的点，要么在$D$中，要么直接连着$D$

Input

第一行两个整数$N,M$，表示有$N$个点，$M$条边，点从1开始编号

接下来$M$行，每行两个整数$u,v$表示$u,v$之间有一条边

输入保证没有重边自环，并且是个二分图

$1\le N \le 30$

$0\le M \le 225$

Output

输出一个整数，表示选择点集的方案

Samples

4 4
1 2
2 3
3 4
4 1

11

4 0

1

Resources

每周一题 div1