EduBrick

M. Пути длины два

2000 мс · 256 МБ · всё или ничего

Ориентированный граф задан списком рёбер. Посчитайте количество путей длины ровно два — то есть пар рёбер вида u→w→vu \to w \to v.

Вершины uu, ww, vv не обязаны быть различными, а рёбра берутся с учётом кратности.

Перебирать пары рёбер нельзя. Заметьте, что каждый такой путь однозначно задаётся своей средней вершиной и выбором входящего и исходящего ребра.

Формат ввода

Первая строка содержит числа nn (1≤n≤1051 \le n \le 10^5) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с парами (u,v)(u, v). Возможны петли и кратные рёбра.

Формат вывода

Одно число — количество путей длины два. Ответ помещается в 64-битный тип.

Примеры

ввод
3 2
1 2
2 3
вывод
1
ввод
1 1
1 1
вывод
1
Войдите, чтобы отправлять решения.