시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB74353044.118%

문제

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.

예제 입력 1

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


예제 출력 1

0
0
1
1
2
6