P5871 [SEERC 2018] Inversion

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 $ip_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}$.

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 the number of independent dominating sets in the graph. It is guaranteed that the answer will not exceed $10^{18}$.

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