P5871 [SEERC 2018] Inversion

定义一个长为 $n$ 的*排列*为一个序列 $p_1, p_2, \dots, p_n$，其中 $[1, n]$ 范围内的整数都恰好在这个序列中出现一次。定义排列中的一个*逆序对*为一对整数 $(i, j)$，其中 $i, j \in [1,n]$，且满足 $ip_j$。 定义一个*逆序对图*为一个有 $n$ 个点的图，图中存在一条 $(i, j)$ 的边当且仅当 $(i,j)$ 是一个逆序对。 定义一个图中的*独立集*为一个图中点的集合，满足集合中的点两两之间没有边相连。定义一个图中的*支配集*为一个图中点的集合，满足不在这个集合中的点都与集合中的某个点有边相连。定义一个图中的*独立支配集*为一个图中点的集合，这个集合既是独立集又是支配集。 给定某一个长为 $n$ 的排列的逆序对图，请计算出这个图中独立支配集的数量。 数据保证答案不会超过 $10^{18}$。

第一行包含两个整数 $n$ 和 $m \ (1 \leq n \leq 100, 0 \leq m \leq \frac{n \times (n-1)}{2})$，代表图中的点数和边数。 接下来 $m$ 行每行包含两个整数 $u_i$ 和 $v_i \ (1 \leq u_i, v_i \leq n)$，代表图中点 $u_i$ 和 $v_i$ 之间有一条边相连。 数据保证图一定对应某一个排列。

输出图中独立支配集的数量。 数据保证答案不会超过 $10^{18}$。

第一个样例中，图对应排列 $[1,4,2,3]$，独立支配集有 $(1,3,4)$ 和 $(1,2)$。 第二个样例中，图对应排列 $[3,5,4,1,2]$，独立支配集有 $(1,2),(1,3),(4,5)$。 第三个样例中，图对应排列 $[2,4,1,5,7,6,3]$。 第四个样例中，图对应排列 $[5,2,1,4,3]$。