EduBrick

Для скольких пар порядок определён

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

В ациклическом графе посчитайте количество упорядоченных пар (u,v)(u, v), для которых в любом топологическом порядке uu идёт раньше vv.

Формат ввода

В первой строке - числа nn и mm (1≤n≤50001 \le n \le 5000, 0≤m≤2⋅1040 \le m \le 2 \cdot 10^4).

В следующих mm строках - рёбра ациклического графа.

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

Выведите количество упорядоченных пар, порядок которых определён однозначно.

Примеры

ввод
3 2
1 2
2 3
вывод
3
ввод
3 0
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.