Monochromatic Triangles

Interview

Time limit1sMemory limit128 MB

Summary

Given n points and a list of red edges (all other pairs are black), count the triangles whose three sides share one color.

Level: Medium5 of 10
Topics: Combinatorics, Graph, Brute force, Implementation
Solved: No attempts yet

Problem

There are $n$ points in the plane, and no three of them are collinear. Every pair of points is joined by a segment colored either red or black. A triangle whose three sides all have the same color is called a monochromatic triangle. Given the list of all red segments, count the monochromatic triangles. Every pair of points not in the list is joined by a black segment.

Write a program that:

reads the number of points, the number of red segments, and their list from standard input,
computes the number of monochromatic triangles,
writes the result to standard output.

Input

The first line contains the number of points $n$ ( $3 \le n \le 1{,}000$ ). The second line contains the number of red segments $m$ ( $0 \le m \le 250{,}000$ ). Each of the next $m$ lines contains two integers $p$ and $k$ , separated by a single space, the endpoints of a red segment ( $1 \le p < k \le n$ ). Every other pair of points is black.

Output

Print a single integer: the number of monochromatic triangles.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
3
0
```
Expected output
```
1
```
Example 3
Input
```
3
3
1 2
1 3
2 3
```
Expected output
```
1
```
Example 4
Input
```
3
1
1 2
```
Expected output
```
0
```