eolymp
bolt
Try our new interface for solving problems

LCA

The directed graph is given. How many pairs of vertices $(i, j)$ have the common ancestor? The common ancestor of vertices $i$ and $j$ is a vertex $k$ for which $i$ and $j$ are reachable from $k$. \InputFile The first line contains the number of vertices $n~(1 \le n \le 10^4)$ and number of edges $m~(0 \le m \le 10^4)$ in a graph. Each of the next $m$ lines contains two numbers from $1$ to $n$. The pair $(a, b)$ means that an edge goes from $a$ to $b$. \OutputFile Print the number of pairs. \includegraphics{https://eolympusercontent.com/images/qrgvlfh2t533500f3smc7q8pic.gif}
Time limit 2 seconds
Memory limit 128 MiB
Input example #1
2 1
1 2
Output example #1
4
Input example #2
3 2
2 1
3 1
Output example #2
7