题目描述

定义一个长为 $n$ 的排列为一个序列 $p_1, p_2, \dots, p_n$，其中 $[1, n]$ 范围内的整数都恰好在这个序列中出现一次。定义排列中的一个逆序对为一对整数 $(i, j)$，其中 $i, j \in [1,n]$，且满足 $i<j, p_i>p_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}$。

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

提示

第一个样例中，图对应排列 $[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]$。