Задано ациклічний орієнтовний граф з 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). Граф не містить петель, циклів і кратних ребер.
Вивести кількість ребер у транзитивному замиканні.