Diamonds

Time limit2sMemory limit1024 MB

Summary

Count the diamonds, which are pairs of triangles sharing an edge, in an undirected graph with up to 300000 vertices and edges.

Level: Medium6 of 10
Topics: Graph, Combinatorics
Solved: No attempts yet

Problem

You have learned that an ancient Inca book describes how to defeat Pennywise. You found the book, but unfortunately it is written in the language of graphs.

To understand one page of the book, you need to count the number of diamonds in the graph drawn on that page.

A diamond in an undirected graph without self-loops and multiple edges is two triangles that share a common edge.

Two diamonds are considered different if there is an edge that belongs to one diamond but not to the other.

Input

The first line contains two integers $n$ and $m$ ( $4 \leq n, m \leq 300\,000$ ), the number of vertices and edges of the graph. Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ( $1 \leq a_i, b_i \leq n$ ; $a_i \neq b_i$ ), the vertices joined by the $i$ -th edge. It is guaranteed that the graph has no multiple edges.

Output

Print one integer, the number of diamonds in the graph.

Examples3

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