К-реберний граф#4603
Задано ациклічний орієнтовний граф з вершинами та ребрами. Знайти кількість ребер у його транзитивному замиканні.
Транзитивним замиканням графу є граф G', який складається з множини вершин заданого графа та множини ребер таких, що існує шлях з вершини у вершину у графі .
Кнут знає, як розв'язати цю задачу, а Ви?
У першому рядку два числа і (1 \le n, k \le 50000). Далі йдуть рядків кожний з яких містить по два цілих числа a_i та b_i. Вони позначають наявність ребра, що веде з вершини a_i у b_i (1 \le a_i, b_i \le n). Граф не містить петель, циклів і кратних ребер.
Вивести кількість ребер у транзитивному замиканні.
Приклад 1