[省选联考 2021 A/B 卷] 图函数

题目描述

对于一张 $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

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

输出样例 #1

6 5 5 4 4 4 4

输入样例 #2

见附件中的 graph/graph2.in。

输出样例 #2

见附件中的 graph/graph2.ans。

说明

**【样例 #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$。 每个测试点的具体限制见下表: | 测试点编号 | $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$ |