favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

# K-edges graph

You are given an acyclic directed graph, consisting of n nodes and k edges. Find the number of edges in its transitive closure.

Transitive closure of graph G is a graph G', consisting of all nodes of original graph G and such edges (u, v) that there is a path from node u to v in graph G.

Knuth knows how to solve the problem. And what about you?

#### Input

The first line contains two numbers n and k (1n, k50000). Then k lines follow, each containing two integers ai and bi, describing directed edge from ai to bi (1ai, bin). Graph doesn't contain loops, cycles and multiple edges.

#### Output

Print the number of edges in transitive closure.

Time limit 2 seconds
Memory limit 512 MiB
Input example #1
5 6
1 2
2 3
3 5
4 5
1 5
1 3

Output example #1
7

Author А. Milanin
Source 2013 Winter School Kharkov, Day 1, Problem K