Monochromatic triangles

Time Limit:1000ms Memory Limit:64000KiB
Accepted:0 Submitted:0
Monochromatic triangles

POI IV Stage III Problem 5

Monochromatic triangles

There are n points given in a space. There are no three points, such that they lie on the same straight line. Each pair of points is connected by a segment coloured red or black. Each triangle, whose sides have the same colour is called a monochromatic triangle. We are given a list of all red segments and we want to find the number of all monochromatic triangles.

Task

Write a program that:
  • reads from the text file TRO.IN the following data: the number of points, the number of red segments and their list,
  • finds the number of monochromatic triangles,
  • writes the result to the text file TRO.OUT.

Input

In the first line of the text file TRO.IN there is one integer n, 3 <= n <= 1000, which equals the number of points.

In the second line of the same file there is one integer m, 0 <= m <= 250000, which equals the number of red segments.

In each of the following m lines there are two integers p and k separated by a single space, 1 <= p < k <= n. They are numbers of vertices which are ends of a red segment.

Output

In the first line of the text file TRO.OUT there should be written one integer - the number of monochromatic triangles.

Example

For the text file TRO.IN:
6 
9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6
the correct solution is the text file TRO.OUT
2

SubmitStatistics

SOJ is designed and developed by Wilbur Ding and Liang Sun. ©All Rights Reserved 2009-2012.