시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 137 | 52 | 45 | 39.474% |
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.
4 6 1 2 2 3 2 1 3 4 4 3 3 2
0 0 1 1 2 6