题目描述

AtCoder Town 有 $N$ 个交叉路口和 $M$ 条道路。第 $i$ 条道路连接着交叉路口 $A_i$ 和 $B_i$。

市长高桥决定在这些交叉路口安装零个或多个监控摄像头。每个交叉路口可以安装零个或一个监控摄像头。

有多少种方法可以安装监控摄像头，使得它们监控的道路数量为偶数？

这里，当满足以下条件时，道路 $i$ 被监控：

在交叉路口 $A_i$ 和/或 $B_i$ 处安装了监控摄像头。

约束条件

• $2 \leq N \leq 40$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i < 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\\}$。
注意，允许不安装监控摄像头。

示例输入 2

20 3
5 6
3 4
1 2

示例输出 2

458752

交叉路口之间可能没有连接。