[ICPC2021 Nanjing R] Ancient Magic Circle in Teyvat


给定一个 $n$ 个点的完全图,有 $m$ 条边是红色的,其余边是蓝色的,求出边均为蓝色的大小为 $4$ 的完全子图个数与边均为红色的大小为 $4$ 的完全子图个数的差。 $4\le n\le 10^5$,$0\le m\le \min(\frac{n(n-1)}{2},2\times 10^5)$。


Astrologist Mona Megistus discovers an ancient magic circle in Teyvat recently. ![](https://cdn.luogu.com.cn/upload/image_hosting/gohzab6t.png) The magic circle looks like a complete graph with $n$ vertices, where $m$ edges are colored red and other edges are colored blue. Note that a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. Mona realizes that if she chooses four different vertices such that the six edges between these four vertices are of the same color, she will get a *key* from the magic circle. If the color is red, she will get a *red key*, and if the color is blue, she will get a *blue key*. Base on the information written in the ancient books Mona has read, the magic power of the ancient magic circle is the absolute difference between the number of *red keys* and the number of the number of *blue keys* she can get from the magic circle. Mona needs your help badly, since calculating the magic power of the magic circle is really a tough job.



There is only one test case in each test file. The first line of the input contains two integers $n$ and $m$ ($4 \le n \le 10^5$, $0 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5)$) indicating the number of vertices and the number of edges colored red of the ancient magic circle. For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($u_i < v_i$) indicating a red edge connecting vertices $u_i$ and $v_i$. It is guaranteed that each edge appears at most once.


Output one line containing one integer indicating the magic power of the ancient magic circle.


输入样例 #1

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

输出样例 #1



For the sample case, there is only one *red key* $(1,2,3,4)$ and there are four *blue keys* $(1,5,6,7)$, $(2,5,6,7)$, $(3,5,6,7)$ and $(4,5,6,7)$ in the ancient magic circle, thus the magic power of the magic circle is $|1-4|=3$.