Подсчет количества треугольников в графе
Дан неориентированный граф с
v вершинами и e рёбрами. Требуется найти количество треугольников в этом графе.Треугольником в графе называется множество из 3 вершин, каждая из которых соединена с двумя другими вершинами из этой тройки.
Например, в графе на рисунке присутствует 3 треугольника:
- 1-2-5
- 2-5-4
- 3-2-4
Входные данные
В первой строке содержится два целых числа
v (1 ≤ v ≤ 100) и e (1 ≤ e ≤ ).В следующих
e строках заданы пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), означающие, что вершина v1 соединена с вершиной v2, и наоборот.Выходные данные
Программа должна вывести количество треугольников в данном графе.
Примеры
Input | Output |
5 7
1 2
1 5
2 5
4 5
2 4
2 3
3 4 | 3 |
3 2
1 2
2 3 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB