← 返回题目列表

AtCoder · abc401_e

H. 可达集

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

分数: 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