给你一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。您必须在此图的每个顶点上写下一个数字,每个数字应该是 $$$0$$$ 或 $$$1$$$。之后,在每条边上写入一个数字,该数字等于与该边相关的顶点上的数字之和。
您必须选择要在顶点上写入的数字,以便至少有一条边上写有 $$$0$$$,至少有一条边上写有 $$$1$$$,并且至少有一条边上写有 $$$2$$$。有多少种方法可以做到?如果存在至少一个顶点以这两种方式写有不同的数字,则两种选择数字的方式是不同的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 40$$$, $$$0 \le m \le \frac{n(n - 1)}{2}$$$) — 分别是顶点数和边数。
接下来是 $$$m$$$ 行,每行包含两个数字 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — 第 $$$i$$$ 条边的端点。保证每对顶点最多由一条边连接。
输出
打印一个整数 — 在所有顶点上写数字的方式的数量,以便存在至少一条边上写有 $$$0$$$,至少一条边上写有 $$$1$$$ 和至少一条边上写有 $$$2$$$。
示例
输入 #1
6 5 1 2 2 3 3 4 4 5 5 1
输出 #1
20
输入 #2
4 4 1 2 2 3 3 4 4 1
输出 #2
4
输入 #3
35 29 1 2 2 3 3 1 4 1 4 2 3 4 7 8 8 9 9 10 10 7 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30
输出 #3
34201047040