E - Reachable Set Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

N 頂点 M 辺からなる無向グラフがあります。 頂点には 1,2,\ldots,N の番号がついており、i 番目 (1\leq i\leq M) の辺は頂点 u _ i と頂点 v _ i を結んでいます。

k=1,2,\ldots,N について、次の問題を解いてください。

次の操作について考える。

  • 頂点を一つ選ぶ。選んだ頂点と、選んだ頂点に接続する全ての辺をグラフから削除する。

上の操作を繰り返すことで、次の条件を満たすことができるか判定せよ。

  • 頂点 1 から辺をたどって到達できる頂点の集合が、頂点 1, 頂点 2,\ldots, 頂点 k のちょうど k 個からなる。

可能な場合、条件を満たすために少なくとも何回操作を行う必要があるか求めよ。

制約

  • 1\leq N\leq2\times10 ^ 5
  • 0\leq M\leq3\times10 ^ 5
  • 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M)
  • (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

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 の 3 つの頂点を選んで削除することで、頂点 1 から到達できる頂点を頂点 1, 頂点 2 の 2 つだけにすることができます。 頂点を 2 つ以下だけ削除して条件を満たすことはできないため、2 行目には 3 を出力してください。

また、k=6 としたときの問題では、頂点をひとつも削除しないことで頂点 1 から到達できる頂点を頂点 1, 頂点 2,\ldots, 頂点 6 の 6 つにすることができます。 なので、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

辺が 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

Score : 450 points

Problem Statement

You are given an undirected graph with N vertices and M edges. The vertices are numbered 1,2,\ldots,N, and the i‑th edge (1 \le i \le M) connects vertices u_i and v_i.

For each k = 1,2,\ldots,N, solve the following problem:

Consider the following operation.

  • Choose one vertex, and delete that vertex together with all edges incident to it.

Determine whether one can repeat this operation to satisfy the following condition:

  • The set of vertices reachable from vertex 1 by traversing edges consists exactly of the k vertices 1,2,\ldots,k.

If it is possible, find the minimum number of operations required to do so.

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print N lines. On the i-th line (1 \le i \le N), if one cannot satisfy the condition for k=i, print -1; otherwise, print the minimum number of operations required to satisfy the condition.

Sample Input 1

6 7
1 2
1 5
2 3
2 4
2 5
3 6
5 6

Sample Output 1

2
3
3
2
1
0

For example, for k = 2, deleting the three vertices 3, 4, 5 makes the set of vertices reachable from vertex 1 equal to the two vertices 1, 2. It is impossible with two or fewer deletions, so print 3 on the 2nd line.

For k = 6, deleting zero vertices makes the set of vertices reachable from vertex 1 equal to the six vertices 1,2,\ldots,6, so print 0 on the 6th line.

Sample Input 2

5 4
1 5
2 3
3 4
4 5

Sample Output 2

1
-1
-1
-1
0

Sample Input 3

2 0

Sample Output 3

0
-1

There may be no edges.

Sample Input 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

Sample Output 4

5
-1
-1
-1
-1
-1
4
3
2
1
0