该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

In order to prepare for the interview, Tianwell​ reviewed the course of Computer Networking. Specially, the C/S mode based on TCP/IP is particularly important. $C$ means the ​client​ and $S$ means the ​server​. In a computer network, any host can be either a ​client​ or a server​. So Tianwell​ came up with an interesting question:

In a network with $n$ hosts and $m$ links, a host can be in both power-on or power-off states. Suppose there is an link $e_i$ that represents the edge directly connected between host $a$ and host $b$. If $a$ and $b$ are turned on at the same time, it means that $e_i$ is **fully activated**. If one of a and b is turned on and the other is turned off, then $e_i$ is **semi-active **and if both a and b are turned off, $e_i$ is **completely disconnected**.

Now you can choose the state of these $n$ hosts and you must ensure that among the $m$ links, at least one link is **fully activated**, at least one is **semi-activated**, and at least one is **fully disconnected**.

Tianwell​ wants to test you, how many options can you figure out the answer with above conditions?  (The difference between the two ways is that at least one host in different state)

输入格式

The first line contains two integers $n$ and $m$ $(1≤n≤40, 0≤m≤\frac{n(n−1)}2)$  — the number of host and the number of links, respectively.

Then $m$ lines follow, each line contains two integers $x_i$ and $y_i$ $(1≤x_i,y_i≤n, x_i≠y_i)$ — the endpoints of the $i_{th}$ link. It is guaranteed that each pair of hosts is connected by at most one link.

输出格式

Print one integer — the number of ways that among the $m$ links, at least one link is **fully activated**, at least one is **semi-activated**, and at least one is **fully disconnected**.

样例

4 4
1 2
2 3
3 4
1 4

4