题目描述

AtCoder 町は $N$ カ所の交差点と、$M$ 本の道からなります。
道 $i$ は、交差点 $A_i$ と交差点 $B_i$ を結んでいます。

髙橋町長は、AtCoder 町の交差点に $0$ 個以上の監視カメラを設置することにしました。
各交差点に設置することのできる監視カメラの数は、 $0$ 個または $1$ 個です。

監視カメラの設置方法は $2^N$ 通りありますが、このうち監視されている道が偶数本になる設置方法は何通りありますか？

ただし、以下の条件が満たされるときに、道 $i$ は監視されていると言います。

交差点 $A_i$ と交差点 $B_i$ の一方または両方に監視カメラが設置されている

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

输出格式

答えを出力せよ。

题目大意

给定一个 $n$ 个点 $m$ 条边的无向图, 对于每个点你可以给它安装一个摄像头或是不装, 对于所有 $2^n$ 种方案中, 有多少方案满足有偶数条边被监控到, 一条边被监控的条件为两个端点至少有一个有摄像头.

3 2
1 2
2 3

6

20 3
5 6
3 4
1 2

458752

提示

制約

• $2\ \leq\ N\ \leq\ 40$
• $1\ \leq\ M\ \leq\ \frac{N(N-1)}{2}$
• $1\ \leq\ A_i\ \lt\ B_i\ \leq\ N$
• $i\ \neq\ j$ ならば $(A_i,B_i)\ \neq\ (A_j,B_j)$
• 入力は全て整数

Sample Explanation 1

監視カメラを設置する交差点として、$ \{\ \}\ ,\ \{\ 2\ \}\ ,\ \{\ 1,2\ \}\ ,\{1,3\},\{2,3\},\{1,2,3\} $ を選んだ場合に条件を満たします。 監視カメラを $1$ つも設置しなくても良いことに注意してください。

Sample Explanation 2

AtCoder 町は連結とは限りません。