19028번 - Link Cut Digraph 다국어

문제

After reading the paper Incremental Topological Ordering and Strong Component Maintenance, you came up with the following problem.

You are given a graph with $n$ vertices. There are no edges initially. There are $m$ operations. Each operation is first to add a given directed edge to the graph, and then to output the number of pairs $(u, v)$ (1ドル \leq u < v \leq n$) such that $u$ is reachable from $v$ and $v$ is reachable from $u$.

Can you implement the algorithm described in the paper in an ICPC contest?

입력

The first line contains two integers $n$ and $m$ (1ドル \leq n \leq 10^5,ドル 1ドル \leq m \leq 2.5 \cdot 10^5$).

Each of the following $m$ lines contains two integers $u$ and $v$ (1ドル \leq u, v \leq n$) indicating a newly added directed edge. Parallel edges and self-loops are allowed.

출력

Output $m$ integers, one per line: the requested number of pairs after adding each given edge.

제한

힌트