Partitioning the Resistance

Byteotia is under occupation, and King Byteasar needs to secretly organize a resistance. He has selected a group of people and now wishes to partition them into two groups:

• Conspirators: They will operate directly in the occupied territory. No two conspirators know each other.
• Support Group: They will operate in free Byteotia. Every pair of people in this group must know each other.

Both groups must be non-empty. Given a list of acquaintance relationships among the selected people, your task is to determine the number of ways to partition them into a conspirators group and a support group so that the following conditions hold:

• If S is the support group then for every pair of distinct people i, j in S, the edge (i, j) must exist (i.e. S forms a clique).
• If C is the conspirators group then for every pair of distinct people i, j in C, the edge (i, j) must not exist (i.e. C forms an independent set).

In mathematical terms, if we denote the support group by S and the conspirators group by C, then the conditions are:

$$ \text{For all } i,j \in S,\; i\neq j,\quad (i,j) \in E, \quad \text{and} \quad \text{for all } i,j \in C,\; i\neq j,\quad (i,j) \notin E. $$

Output the total number of valid partitions, or 0 if no such partition exists.

inputFormat

The input begins with a line containing two integers n and m (2 ≤ n ≤ 20, 0 ≤ m ≤ n(n-1)/2), where n is the number of people and m is the number of acquaintance pairs.

Following this, there are m lines, each containing two integers u and v (1 ≤ u, v ≤ n, u ≠ v), indicating that person u and person v know each other. The relationships are undirected.

outputFormat

Output a single integer – the number of valid partitions of the selected people into two groups satisfying the conditions described.

sample

3 2
1 2
2 3

3