K-edges graph#4603
You are given an acyclic directed graph, consisting of nodes and edges. Find the number of edges in its transitive closure.
Transitive closure of graph is a graph G', consisting of all nodes of original graph and such edges (, ) that there is a path from node to in graph .
Knuth knows how to solve the problem. And what about you?
The first line contains two numbers and (1 \le n, k \le 50000). Then lines follow, each containing two integers a_i and b_i, describing directed edge from a_i to b_i (1 \le a_i, b_i \le n). Graph doesn't contain loops, cycles and multiple edges.
Print the number of edges in transitive closure.
Example 1