分数: 450 点
问题陈述
给你一个无向图 N 顶点和 M 边缘。 顶点已编号 1,2,\ldots,N,以及 i第一条边 (1 \le i \le M) 连接顶点 u_i 和 v_i.
对于每个 k = 1,2,\ldots,N,解决以下问题:
考虑以下操作。
- 选择一个顶点,然后删除该顶点以及与其关联的所有边。
判断是否可以重复该操作以满足以下条件:
- 从顶点可到达的顶点集 1 通过遍历边完全由 k 顶点 1,2,\ldots,k.
如果可能,请找出执行此操作所需的最少操作数。
约束
- 1 \le N \le 2 \times 10^{5}
- 0 \le M \le 3 \times 10^{5}
- 1 \le u_i < v_i \le N\ (1 \le i \le M)
- (u_i,v_i) \ne (u_j,v_j)\ (1 \le i < j \le M)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
打印 N 行。上 i第行 (1 \le i \le N),如果不能满足条件 k=i,打印 -1;否则,打印满足条件所需的最少操作数。
示例输入 1
6 7 1 2 1 5 2 3 2 4 2 5 3 6 5 6
示例输出 1
2 3 3 2 1 0
例如,对于 k = 2,删除三个顶点 3, 4, 5 使顶点集可从顶点到达 1 等于两个顶点 1, 2。
两次或更少的删除是不可能的,所以打印 3 在第二行。
对于 k = 6,删除零个顶点使得顶点集可以从顶点到达 1 等于六个顶点 1,2,\ldots,6,所以打印 0 在第六行。
示例输入 2
5 4 1 5 2 3 3 4 4 5
示例输出 2
1 -1 -1 -1 0
示例输入 3
2 0
示例输出 3
0 -1
可能没有边缘。
示例输入 4
11 25 6 9 5 9 2 3 1 9 10 11 4 5 9 10 8 9 7 8 3 5 1 7 6 10 4 7 7 9 1 10 4 11 3 8 2 7 3 4 1 8 2 8 3 7 2 10 1 6 6 11
示例输出 4
5 -1 -1 -1 -1 -1 4 3 2 1 0