e-olymp
Competitions

IOI Preparation - Trees

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