当前没有测试数据。

题目描述

In graph theory, an independent set is a set of nonadjacent vertices in a graph. Moreover, an independent set is maximum if it has the maximum cardinality (in this case, the number of vertices) across all independent sets in a graph.

An induced subgraph G'(V', E') of a graph G(V, E) is a graph that satisfies:

• $V' \subseteq V$

• edge $(a,b) \in E'$ if and only if $a \in V', b \in V'$, and edge $(a, b) \in E$;

Now, given an undirected unweighted graph consisting of n vertices and m edges. This problem is about the cardinality of the maximum independent set of each of the $2^n$ possible induced subgraphs of the given graph. Please calculate the sum of the $2^n$ such cardinalities.

输入格式

The first line contains two integers n and m ($ 2 \le n \le 26, 0 \le m \le \frac{n \times (n-1)}{2} $) --- the number of vertices and the number of edges, respectively. Next m lines describe edges: the i-th line contains two integers $x_i, y_i$​ ($0 \le x_i < y_i < n$) --- the indices (numbered from 0 to n - 1) of vertices connected by the i-th edge.

The graph does not have any self-loops or multiple edges.

输出格式

Print one line, containing one integer represents the answer.

样例

样例输入 1

3 2
0 1
0 2

样例输出 1

9

样例解释 1

The cardinalities of the maximum independent set of every subset of vertices are: {}: 0, {0}: 1, {1}: 1, {2}: 1, {0, 1}: 1, {0, 2}: 1, {1, 2}: 2, {0, 1, 2}: 2. So the sum of them are 9.

样例输入 2

7 5
0 5
3 4
1 2
2 5
0 2

样例输出 2

328