← 返回题目列表

AtCoder · abc446_f

I. 可到达的组 2

中文机器翻译题面 查看原题

分数: 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 可能具有多边或自环。