Inversion

Time limit1sMemory limit512 MB

Summary

Given the inversion graph of a permutation on at most 100 vertices, count its independent sets that also dominate every vertex outside. The answer fits in 10^18.

Level: Hard8 of 10
Topics: Graph, Brute force, Backtracking, Bit manipulation
Solved: No attempts yet

Problem

A sequence $p_1, p_2, \ldots, p_n$ is called a permutation of the numbers $1, 2, \ldots, n$ if every number in the range $[1, n]$ appears in it exactly once. A pair $(i, j)$ of integers with $1 \le i, j \le n$ is called an inversion if $i < j$ and $p_i > p_j$ .

An inversion graph is a graph with exactly $n$ vertices in which there is an edge between the pair $(i, j)$ if and only if that pair is an inversion.

A set $s$ of vertices of a graph is called independent if no two vertices from this set have an edge between them. A set $t$ of vertices of a graph is called dominant if every vertex that does not belong to the set has an edge to at least one vertex that belongs to it. A set $g$ of vertices of a graph is called independent-dominant if it is both dominant and independent.

You are given the inversion graph of a particular permutation of $1, 2, \ldots, n$ , defined by the pairs of vertices $(a_i, b_i)$ that have an edge between them. Find the number of independent-dominant sets of the graph.

The answer is guaranteed not to exceed $10^{18}$ .

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 100$ , $0 \le m \le n \times (n-1)/2$ ), the number of vertices of the graph and the number of edges in the graph.

Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ( $1 \le u_i, v_i \le n$ ), which means that there is an edge between $u_i$ and $v_i$ .

It is guaranteed that there exists a permutation that gives this graph.

Output

Print the number of independent-dominant sets of vertices of the graph.

The answer is guaranteed not to exceed $10^{18}$ .

Notes

The first sample is the graph for permutation $[1, 4, 2, 3]$ . We can select two sets of nodes: $(1, 3, 4)$ or $(1, 2)$ .

The second sample is the graph for permutation $[3, 5, 4, 1, 2]$ . We can select three sets of nodes: $(1, 2)$ , $(1, 3)$ , $(4, 5)$ .

The third sample is a graph for permutation $[2, 4, 1, 5, 7, 6, 3]$ .

The fourth sample is a graph for permutation $[5, 2, 1, 4, 3]$ .

Examples4

Example 1
Input
```
4 2
2 3
2 4
```
Expected output
```
2
```
Example 2
Input
```
5 7
2 5
1 5
3 5
2 3
4 1
4 3
4 2
```
Expected output
```
3
```
Example 3
Input
```
7 7
5 6
2 3
6 7
2 7
3 1
7 5
7 4
```
Expected output
```
6
```
Example 4
Input
```
5 6
1 3
4 5
1 4
2 3
1 2
1 5
```
Expected output
```
5
```