Guard Placement in Trench Systems

Near a military base there is a system of trenches, modeled as line segments on a plane. During the night, when most soldiers are asleep, three guards are dispatched to watch over the trenches. Two guards see each other if there exists a trench (or a concatenation of collinear trenches) along the complete straight line segment joining them, and no third guard is placed between them on that segment.

For security reasons, the guards must be positioned so that each guard sees the other two. It turns out that if we restrict placements to certain strategic points (which are the endpoints and intersection points of the trenches), the condition is equivalent to demanding that every pair of chosen points is connected by a direct trench segment (i.e. they are adjacent in the trench graph) and no guard lies between them.

This reduces the problem to counting the number of triangles in an undirected graph. In other words, given a graph with n vertices and m edges, count the number of triples of distinct vertices \( (i, j, k) \) with \( i < j < k \) such that the edges \((i,j)\), \((j,k)\) and \((i,k)\) are all present.

Note: Two guards can see each other if and only if they are connected by an edge and no third guard lies in between them along that edge. For any valid triangle, since each edge directly connects two vertices, the additional condition is automatically satisfied.

The task is to calculate the number of valid placements (i.e., triangles in the graph) that meet the above conditions.

The necessary condition for a triangle is:

[ edge(i,j) \wedge edge(j,k) \wedge edge(i,k) ]

inputFormat

The input begins with a line containing two integers n and m denoting the number of vertices and the number of edges in the trench system, respectively. The vertices represent the strategic points where guards can be placed, and each edge represents a direct trench segment between two points.

This is followed by m lines, each containing two integers u and v (1-indexed), indicating that there is an undirected edge (trench segment) connecting vertex u and vertex v.

outputFormat

Output a single integer representing the number of ways to place the three guards so that every guard sees the other two (i.e. the number of triangles in the graph).

sample

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

4