分数: 500 点
问题陈述
给你一个有向图 G 与 N 顶点和 M 边缘。
的顶点 G 被编号为顶点 1,顶点 2, \ldots,顶点 N,以及 i第边缘 (1\leq i\leq M) 从顶点出发 U_i 到顶点 V_i.
解决以下问题 k=1,2,\ldots,N.
Takahashi 的目标是删除一些(可能是零)顶点 G,以及以这些顶点为端点的所有边,从而满足以下条件。
- 从顶点可到达的唯一顶点 1 通过遍历零个或多个边得到顶点 1,2,\ldots,k.
确定他是否可以实现他的目标,如果可以,找到他需要删除的最少顶点数才能实现它。
约束
- 2\leq N\leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 1\leq U_i,V_i\leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
5 5 1 2 2 4 2 5 4 3 4 5
示例输出 1
1 2 -1 1 0
- 对于 k=1,通过删除顶点即可达到目的 2。注意顶点 3,4,5 已经无法从顶点到达 1 而不删除它们。如果不删除至少一个顶点就无法实现目标,因此输出 1 在第一行。
- 对于 k=2,通过删除顶点即可达到目的 4 和 5。删除一个或更少的顶点是不可能达到目的的,所以输出 2 在第二行。
- 对于 k=3,高桥无论怎么删除顶点都无法达到目的。因此,输出 -1 在第三行。
- 对于 k=4,通过删除顶点即可达到目的 5。如果不删除至少一个顶点就无法实现目标,因此输出 1 在第四行。
- 对于 k=5,无需删除任何顶点即可达到目的。因此,输出 0 第五行。
示例输入 2
5 5 1 1 1 2 3 1 3 1 3 5
示例输出 2
1 0 -1 -1 -1
G 不一定相连。另外, G 可能具有多边或自环。