如果一个序列 $p_1, p_2, \dots, p_n$ 中 $1$ 到 $n$ 的每个数字都恰好出现一次，则称其为 $n$ 的一个排列。若 $i < j$ 且 $p_i > p_j$，则称整数对 $(i, j)$ 为一个逆序对。 我们将逆序图定义为一个恰好有 $n$ 个顶点的图，当且仅当 $(i, j)$ 为逆序对时，顶点 $i$ 和 $j$ 之间存在一条边。

图中的一个顶点集合 $s$ 被称为独立集，如果该集合中任意两个顶点之间都没有边。图中的一个顶点集合 $t$ 被称为支配集，如果图中所有不属于该集合的顶点都与该集合中的至少一个顶点有边相连。如果一个顶点集合 $g$ 既是支配集又是独立集，则称其为独立支配集。

你拥有一个特定排列 $1, 2, \dots, n$ 的逆序图，该图由顶点对 $(a_i, b_i)$ 定义，这些顶点对之间存在边。请找出该图中独立支配集的数量。 题目保证答案不超过 $10^{18}$。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 100, 0 \le m \le \frac{n(n-1)}{2}$)，分别表示图的顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示 $u_i$ 和 $v_i$ 之间存在一条边。 题目保证存在一个能生成该图的排列。

输出格式

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

样例

输入 1

4 2
2 3
2 4

输出 1

2

输入 2

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

输出 2

3

输入 3

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

输出 3

6

输入 4

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

输出 4

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]$ 的图。