Link Cut Digraph

정점이 $n$개인 그래프가 있으며, 처음에는 간선이 없다. 연산은 $m$번 수행한다. 각 연산에서는 주어진 방향 간선을 그래프에 추가한 뒤, $u$에서 $v$로 도달할 수 있고 $v$에서 $u$로 도달할 수 있는 쌍 $(u, v)$ ($1 \leq u < v \leq n$)의 개수를 출력한다.

ICPC 대회에서 논문에 나온 알고리즘을 구현할 수 있는가?

첫 줄에 두 정수 $n$, $m$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 2.5 \cdot 10^5$)이 주어진다. 이후 $m$개의 줄에는 새로 추가되는 방향 간선을 나타내는 두 정수 $u$, $v$ ($1 \leq u, v \leq n$)가 한 줄에 하나씩 주어진다. 병렬 간선과 자기 루프가 허용된다.

$m$개의 정수를 한 줄에 하나씩 출력한다. 각 정수는 해당 간선을 추가한 뒤의 쌍의 개수이다.