Дан ациклический ориентированный граф из n вершин и k рёбер. Найти количество рёбер в его транзитивном замыкании.
Транзитивное замыкание графа G - граф G', состоящий из множества вершин исходного графа G и множества ребер (u, v) таких, что существует путь из вершины u в вершину v в графе G.
Кнут знает, как решать эту задачу. А Вы?
В первой строке два числа n и k (1 ≤ n, k ≤ 50000). В каждой из следующих k строк находится по два целых числа a[i]
и b[i]
, означающих наличие ребра, ведущего из вершины a[i]
в b[i]
(1 ≤ a[i]
, b[i]
≤ n). Граф не содержит петель, циклов и кратных рёбер.
Вывести количество рёбер в транзитивном замыкании.