eolymp
bolt
Try our new interface for solving problems
Problems

K-edges graph

K-edges graph

Time limit 2 seconds
Memory limit 512 MiB

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 data

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

Output data

Print the number of edges in transitive closure.

Examples

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