9598 - 图函数

对于一张 n 个点 m 条边的有向图 G（顶点从 1 \sim n 编号），定义函数 f(u, G)：

1. 初始化返回值 cnt = 0，图 G' = G。
2. 从 1 至 n 按顺序枚举顶点 v，如果当前的图 G' 中，从 u 到 v 与从 v 到 u 的路径都存在，则将 cnt + 1，并在图 G' 中删去顶点 v 以及与它相关的边。
3. 第 2 步结束后，返回值 cnt 即为函数值。

现在给定一张有向图 G，请你求出 h(G) = f(1, G) + f(2, G) + \cdots + f(n, G) 的值。

更进一步地，记删除（按输入顺序给出的）第 1 到 i 条边后的图为 G_i（1 \le i \le m），请你求出所有 h(G_i) 的值。

第一行，两个整数 n,m，表示图的点数与边数。
接下来 m 行，每行两个整数，第 i 行的两个整数 x_i, y_i 表示一条有向边 x_i \to y_i。

数据保证 x_i \neq y_i 且同一条边不会给出多次。

输出一行 m + 1 个整数，其中第一个数表示给出的完整图 G 的 h(G) 值。第 i（2 \le i \le m + 1）个整数表示 h(G_{i-1})。

【样例 #1 解释】

对于给出的完整图 G：

1. f(1, G) = 1，过程中删除了顶点 1。
2. f(2, G) = 1，过程中删除了顶点 2。
3. f(3, G) = 2，过程中删除了顶点 2, 3。
4. f(4, G) = 2，过程中删除了顶点 1, 4。

【数据范围】

对于所有测试数据：2 \le n \le {10}^3，1 \le m \le 2 \times {10}^5，1 \le x_i, y_i \le n。

联合省选