Description

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)$.

Input Format

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 Format

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})$.

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

6 5 5 4 4 4 4

见附件中的 graph/graph2.in。

见附件中的 graph/graph2.ans。

Hint

[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:

Translated by ChatGPT 5