Short Irreducible Paths (PY)

A path of length k ≥ 0 in an undirected graph is a sequence of k pairwise distinct edges such that each two neighbour edges in the sequence share exactly one endnode and no three edges in the sequence share a common endnode. Also, the first and the last edge in the path share a common node only in case when the length of the path is at most 2.
We say that a node is in path P if it is an endnode of at least one edge in P. We say that a path P in a graph G is an irreducible path if no edge which is in G and not in P connects two nodes which are in P.

   

Image 1. Graphs a), b), c) corresponding to Examples 1, 2, 3 below. There are 2, resp. 0, resp. 7 irreducible paths of length 3 in the graph a), resp. graph b), resp. graph c).
The paths connect the nodes: a) 3 – 0 – 1 – 2, 0 – 1 – 2 – 5,
c) 0 – 2 – 5 – 6, 0 – 3 – 5 – 4, 1 – 0 – 2 – 4, 1 – 0 – 2 – 5, 1 – 3 – 2 – 4, 1 – 3 – 5 – 4, 4 – 2 – 3 – 6.  

The task

Find the number of irreducible paths of length 3 in a given simple undirected graph.

Input

The first input line contains two integers N and M separated by space. The values indicate (in this order) the number of nodes in the graph and the number of edges in the graph. The nodes are labeled by integers 0, 1, ..., N−1. Next, there are M text lines, each describe one edge. Each line contains the labels of two endnodes of an edge, separated by space. The order of node labels on a line and the order of edges in the input is arbitrary.
It holds, 2 ≤ N ≤ 1000, 1 ≤ M ≤ 3000.

Output

The output contains one text line with one integer representing the number of irreducible paths of length 3 in the input graph.

Example 1

Input
6 9
0 1
1 2
2 5
5 4
4 3
3 0
4 0
4 1
4 2
Output
2
The graph presented in Example 1 is depicted in Image 1a).

Example 2

Input
5 9
0 1
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
Output
0
The graph presented in Example 2 is depicted in Image 1b).

Example 3

Input
7 11
0 1
2 3
4 5
5 6
0 2
2 4
1 3
3 5
0 3
3 6
2 5
Output
7
The graph presented in Example 3 is depicted in Image 1c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set