Competitions

# Shortest paths - interesting graph problems

# 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** (**1** ≤ **n**, **k** ≤ **50000**). Then **k** lines follow, each containing two integers `a`

and _{i}`b`

, describing directed edge from _{i}`a`

to _{i}`b`

(_{i}**1** ≤ `a`

, _{i}`b`

≤ _{i}**n**). Graph doesn't contain loops, cycles and multiple edges.

#### Output

Print the number of edges in transitive closure.

Input example #1

5 6 1 2 2 3 3 5 4 5 1 5 1 3

Output example #1

7