/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
AtCoder 町は N カ所の交差点と、M 本の道からなります。
道 i は、交差点 A_i と交差点 B_i を結んでいます。
髙橋町長は、AtCoder 町の交差点に 0 個以上の監視カメラを設置することにしました。
各交差点に設置することのできる監視カメラの数は、 0 個または 1 個です。
監視カメラの設置方法は 2^N 通りありますが、このうち監視されている道が偶数本になる設置方法は何通りありますか？
ただし、以下の条件が満たされるときに、道 i は監視されていると言います。
交差点 A_i と交差点 B_i の一方または両方に監視カメラが設置されている
制約
- 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)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
答えを出力せよ。
入力例 1
3 2 1 2 2 3
出力例 1
6
監視カメラを設置する交差点として、 \{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\} を選んだ場合に条件を満たします。
監視カメラを 1 つも設置しなくても良いことに注意してください。
入力例 2
20 3 5 6 3 4 1 2
出力例 2
458752
AtCoder 町は連結とは限りません。
Score : 600 points
Problem Statement
AtCoder Town has N intersections and M roads.
Road i connects Intersections A_i and B_i.
Takahashi, the mayor, has decided to install zero or more surveillance cameras at the intersections.
Each intersection can be installed with zero or one surveillance camera.
How many of the 2^N ways to install surveillance cameras monitor an even number of roads?
Here, Road i is said to be monitored when the following condition is satisfied:
a surveillance camera is installed at one or both of Intersections A_i and B_i.
Constraints
- 2 \leq N \leq 40
- 1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq A_i \lt B_i \leq N
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Print the answer.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
6
The sets of towns to install surveillance cameras to satisfy the condition are: \{ \} , \{ 2 \} , \{ 1,2 \} ,\{1,3\},\{2,3\},\{1,2,3\}.
Note that it is allowed to install no surveillance camera.
Sample Input 2
20 3 5 6 3 4 1 2
Sample Output 2
458752
The town may not be connected.