Problem Statement

We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects Vertex $A_i$ and Vertex $B_i$. Find the number of ways to paint each vertex in this graph red, green, or blue so that the following condition is satisfied:

• two vertices directly connected by an edge are always painted in different colors.

Here, it is not mandatory to use all the colors.

Constraints

• $1 \le N \le 20$
• $0 \le M \le \frac{N(N - 1)}{2}$
• $1 \le A_i \le N$
• $1 \le B_i \le N$
• The given graph is simple (that is, has no multi-edges and no self-loops).

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_M B_M

Output

Print the answer.