AT_abc446_f.[ABC446F] Reachable Set 2

给定一个有向图 $G$，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 $1,2,\ldots,N$，第 $i$ 条边（$1\leq i\leq M$）从顶点 $U_i$ 指向顶点 $V_i$。

需要你分别对 $k=1,2,\ldots,N$ 依次解决以下问题：

高桥的目标是从 $G$ 中删去一些（可以为零个）顶点，并一并移除所有以这些顶点为端点的边，使得下述条件得到满足。

• 从顶点 $1$ 出发，通过若干条边（可为零条）可达的所有顶点，恰好为顶点 $1,2,\ldots,k$。

判断他是否可以实现这一目标，如果可以，求最少需要删去多少个顶点才能实现。

输入从标准输入读入，格式如下：

$N\ M\ U_1\ V_1\ U_2\ V_2\ \vdots\ U_M\ V_M$

输出 $N$ 行。
第 $i$ 行（$1\leq i\leq N$）输出针对 $k=i$ 时问题的答案。如果高桥无法实现目标，输出 $-1$；否则输出实现目标所需删去的最小顶点数。

样例说明 1

• 当 $k=1$ 时，可以通过删除顶点 $2$ 实现目标。注意，顶点 $3,4,5$ 即使不删除也已不可达。不能做到不删顶点，因此第 $1$ 行输出 $1$。
• 当 $k=2$ 时，可以通过删除顶点 $4$ 和 $5$ 实现目标。无法只删一个或更少顶点实现，因此第 $2$ 行输出 $2$。
• 当 $k=3$ 时，无论如何删除顶点都无法实现目标，因此第 $3$ 行输出 $-1$。
• 当 $k=4$ 时，可以通过删除顶点 $5$ 实现目标，需要删去至少一个顶点，因此第 $4$ 行输出 $1$。
• 当 $k=5$ 时，无需删除任何顶点就可实现目标，因此第 $5$ 行输出 $0$。

样例说明 2

$G$ 不一定连通，且可能含有重边或自环。

数据范围

• $2\leq N\leq 3\times 10^5$
• $1\leq M\leq 3\times 10^5$
• $1\leq U_i, V_i\leq N$
• 所有输入均为整数。

由 ChatGPT 5 翻译