Counting Feasible Data Structure Problems

In this problem, we consider a scenario where there are n modification operations used in designing data structure problems. Each operation is numbered from 1 to n. There are m mutually exclusive pairs of operations. Each pair \((u_i, v_i)\) indicates that if both operation \(u_i\) and \(v_i\) are chosen in a problem then the problem becomes unsolvable. A problem is feasible if it does not contain any mutually exclusive pair (i.e. no pair \((u_i,v_i)\) such that both operations are selected).

It is also given that any two operations are connected by a chain of mutually exclusive pairs and that \(m-n\) is a very small number. Two problems are considered different if there is at least one operation that appears in one problem and not in the other.

Your task is to count the number of different feasible problems (that is, the number of subsets of \(\{1,2,\dots,n\}\) that do not contain any forbidden pair). Note that the empty set is also a valid feasible problem.

The condition for a problem being feasible is that for every mutually exclusive pair \((u,v)\) the subset does not contain both \(u\) and \(v\) simultaneously.

For instance, if \(n=3\) and there is a single mutually exclusive pair \((1,2)\), then there are \(8\) total subsets. Among these, subsets that contain both \(1\) and \(2\) are not allowed. Hence, the answer would be \(8-2=6\).

inputFormat

The first line contains two integers n and m \((1 \leq n \leq N,\ m \geq n-1)\) denoting the number of operations and the number of mutually exclusive pairs, respectively.

The following m lines each contain two integers \(u_i\) and \(v_i\) \((1 \leq u_i, v_i \leq n,\ u_i \neq v_i)\) representing a mutually exclusive pair of operations.

Note: It is guaranteed that the operations form a connected structure with respect to these mutually exclusive relationships and that \(m-n\) is a very small number, so you may assume n is small enough for a solution using bitmask enumeration.

outputFormat

Output a single integer, the number of feasible subsets (problems) that can be formed.

sample

3 1
1 2

6