P7516 [NOI Qualifier Joint Contest 2021 A/B] Graph Function.

For a directed graph $G$ with $n$ vertices and $m$ edges (vertices are numbered from $1$ to $n$), define the function $f(u, G)$: 1. Initialize the return value $cnt = 0$, and set $G' = G$. 2. Enumerate vertices $v$ from $1$ to $n$ in order. If, in the current graph $G'$, there exists a path from $u$ to $v$ and also a path from $v$ to $u$, then increase $cnt$ by $1$, and delete vertex $v$ from $G'$ together with all edges incident to it. 3. After step 2 ends, return $cnt$ as the function value. Now you are given a directed graph $G$. Compute $h(G) = f(1, G) + f(2, G) + \cdots + f(n, G)$. Furthermore, let $G_i$ ($1 \le i \le m$) be the graph after deleting edges $1$ through $i$ (in the input order). Compute all values $h(G_i)$.

The first line contains two integers $n, m$, denoting the number of vertices and the number of edges in the graph. The next $m$ lines each contain two integers. The two integers $x_i, y_i$ on line $i$ represent a directed edge $x_i \to y_i$. The data guarantees that $x_i \neq y_i$, and no edge is given more than once.

Output one line with $m + 1$ integers. The first integer is $h(G)$ for the complete graph $G$. The $i$-th integer ($2 \le i \le m + 1$) is $h(G_{i-1})$.

**[Sample #1 Explanation]** For the complete graph $G$: 1. $f(1, G) = 1$, and vertex $1$ is deleted during the process. 2. $f(2, G) = 1$, and vertex $2$ is deleted during the process. 3. $f(3, G) = 2$, and vertices $2, 3$ are deleted during the process. 4. $f(4, G) = 2$, and vertices $1, 4$ are deleted during the process. --- **[Constraints]** For all testdata: $2 \le n \le {10}^3$, $1 \le m \le 2 \times {10}^5$, $1 \le x_i, y_i \le n$. The specific limits for each test point are shown in the table below: | Test Point ID | $n \le$ | $m \le$ | |:-:|:-:|:-:| | $1 \sim 4$ | $10$ | $10$ | | $5 \sim 11$ | $100$ | $2 \times {10}^3$ | | $12 \sim 20$ | ${10}^3$ | $5 \times {10}^3$ | | $21 \sim 25$ | ${10}^3$ | $2 \times {10}^5$ | Translated by ChatGPT 5