Game theory is an interesting subject in computer science.
SG function is an important concept in game theory. Given a directed acyclic graph with vertex set and directed edge set , for each vertex , its SG function sg(u) is defined as:

where given a set S of non-negative integers, is defined as the smallest non-negative integer which is not in S.
Today, Rikka wants to generalize SG function to undirected graphs. Given an undirected graph G with vertex set V and undirected edge set E, a function f over V is a valid SG function on G if and only if:
Under this definition, there may be many valid SG functions for a graph. Therefore, Rikka wants to further figure out whether there is a connection between these valid SG functions. As the first step, your task is to calculate the number of valid SG functions for a given undirected graph G.

The first line contains two integers , representing the number of vertices and edges in the graph.
Then m lines follow. Each line contains two integers , representing an edge in the graph.
The input guarantees that there are no loops and duplicate edges in the graph.

Output a single line with a single integer, representing the number of valid SG functions.

5 4
1 2
2 3
3 4
4 5

6

For simplicity, we use list  to represent a function f. 
For the sample input, there are 6 valid SG functions: [0,1,0,1,0], [0,1,2,0,1], [0,2,1,0,1], [1,0,1,0,1], [1,0,1,2,0] and [1,0,2,1,0].