Description

A permutation of length $n$ is defined as a sequence $p_1, p_2, \dots, p_n$, where every integer in the range $[1, n]$ appears in this sequence exactly once. An inversion pair in a permutation is defined as a pair of integers $(i, j)$, where $i, j \in [1,n]$, and it satisfies $i<j, p_i>p_j$.

An inversion graph is defined as a graph with $n$ vertices, where an edge $(i, j)$ exists if and only if $(i,j)$ is an inversion pair.

An independent set in a graph is a set of vertices such that no two vertices in the set are connected by an edge. A dominating set in a graph is a set of vertices such that every vertex not in the set is adjacent to some vertex in the set. An independent dominating set in a graph is a set of vertices that is both an independent set and a dominating set.

Given the inversion graph of a permutation of length $n$, compute the number of independent dominating sets in this graph.

It is guaranteed that the answer will not exceed $10^{18}$.

Input Format

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

The next $m$ lines each contain two integers $u_i$ and $v_i \ (1 \leq u_i, v_i \leq n)$, indicating that there is an edge between vertices $u_i$ and $v_i$.

It is guaranteed that the graph corresponds to some permutation.

Output Format

Output the number of independent dominating sets in the graph.

It is guaranteed that the answer will not exceed $10^{18}$.

4 2
2 3
2 4

2

5 7
2 5
1 5
3 5
2 3
4 1
4 3
4 2

3

7 7
5 6
2 3
6 7
2 7
3 1
7 5
7 4

6

5 6
1 3
4 5
1 4
2 3
1 2
1 5

5

Hint

In the first sample, the graph corresponds to the permutation $[1,4,2,3]$, and the independent dominating sets are $(1,3,4)$ and $(1,2)$.

In the second sample, the graph corresponds to the permutation $[3,5,4,1,2]$, and the independent dominating sets are $(1,2)$, $(1,3)$, and $(4,5)$.

In the third sample, the graph corresponds to the permutation $[2,4,1,5,7,6,3]$.

In the fourth sample, the graph corresponds to the permutation $[5,2,1,4,3]$.

Translated by ChatGPT 5