简单无向图是指不包含自环或重边的无向图。

平面图是一种简单无向图，它可以嵌入平面中，即可以画在平面上，使得它的边仅在公共端点处相交。换句话说，它可以画成没有任何边交叉的形式。

独立集是图中的一个顶点集合，其中任意两个顶点都不相邻。

三部图是一种简单无向图，其顶点可以划分为三个互不相交的独立集。

给定一个平面图。你准备在其中添加一条边。已知无法添加任何一条边使得所得图仍为平面图。请问有多少种添加边的方法，使得所得图是三部图？

注意，你不能添加重边或自环，因为所得图必须是简单图。边 $a - b$ 和 $b - a$ 是相同的，应只计算一次。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($3 \le n, m \le 3 \cdot 10^5$)，分别表示顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，表示顶点 $a$ 和 $b$ 之间有一条边。

保证图符合上述条件。

输出格式

输出一个整数，表示添加一条边使得所得图为三部图的方法数。

样例

样例输入 1

3 3
1 2
1 3
2 3

样例输出 1

0

样例输入 2

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

样例输出 2

0

样例输入 3

8 18
1 2
1 3
1 4
1 5
1 6
1 7
2 3
3 4
4 5
5 6
6 7
2 7
8 2
8 3
8 4
8 5
8 6
8 7

样例输出 3

3

说明

最后一个样例难道不优美且简洁吗？