F - Reachable Set 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の有向グラフ G が与えられます。
G の頂点は頂点 1 、頂点 2 、\ldots 、頂点 N と番号付けられており、 i 番目 (1\leq i\leq M) の辺は頂点 U_i から頂点 V_i へ向かう辺です。

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

高橋君の目標は、G から（0 個でも良い）いくつかの頂点、およびそれらの頂点を始点または終点として持つすべての辺を削除することで、次の条件をみたすようにすることです。

  • 頂点 1 から 0 本以上のいくつかの辺を辿って到達可能な頂点が頂点 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 つも頂点を削除せずに目標を達成することはできないため、1 を 1 行目に出力します。
  • k=2 のとき、頂点 4,5 を削除することにより目標を達成できます。1 つ以下の頂点を削除することによって目標を達成することは不可能なので、2 を 2 行目に出力します。
  • k=3 のとき、高橋君はどのように頂点を削除しても目標を達成できません。よって、-1 を 3 行目に出力します。
  • k=4 のとき、頂点 5 を削除することによって目標を達成できます。1 つも頂点を削除せずに目標を達成することはできないため、1 を 4 行目に出力します。
  • k=5 のとき、頂点を削除することなく目標を達成できます。よって、0 を 5 行目に出力します。

入力例 2

5 5
1 1
1 2
3 1
3 1
3 5

出力例 2

1
0
-1
-1
-1

G は連結とは限りません。また、G は多重辺や自己ループを持つこともあります。

Score : 500 points

Problem Statement

You are given a directed graph G with N vertices and M edges.
The vertices of G are numbered as vertex 1, vertex 2, \ldots, vertex N, and the i-th edge (1\leq i\leq M) goes from vertex U_i to vertex V_i.

Solve the following problem for k=1,2,\ldots,N.

Takahashi's goal is to delete some (possibly zero) vertices from G, along with all edges having those vertices as an endpoint, so that the following condition is satisfied.

  • The only vertices reachable from vertex 1 by traversing zero or more edges are vertices 1,2,\ldots,k.

Determine whether he can achieve his goal, and if so, find the minimum number of vertices he needs to delete to achieve it.

Constraints

  • 2\leq N\leq 3\times 10^5
  • 1\leq M\leq 3\times 10^5
  • 1\leq U_i,V_i\leq N
  • 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

Output N lines.
The i-th line (1\leq i\leq N) should contain the answer to the problem for k=i.
Here, for each problem, output -1 if it is impossible for Takahashi to achieve his goal, and otherwise output the minimum number of vertices that need to be deleted to achieve his goal.

Sample Input 1

5 5
1 2
2 4
2 5
4 3
4 5

Sample Output 1

1
2
-1
1
0
  • For k=1, the goal can be achieved by deleting vertex 2. Note that vertices 3,4,5 are already unreachable from vertex 1 without deleting them. The goal cannot be achieved without deleting at least one vertex, so output 1 on the first line.
  • For k=2, the goal can be achieved by deleting vertices 4 and 5. It is impossible to achieve the goal by deleting one or fewer vertices, so output 2 on the second line.
  • For k=3, Takahashi cannot achieve the goal no matter how he deletes vertices. Thus, output -1 on the third line.
  • For k=4, the goal can be achieved by deleting vertex 5. The goal cannot be achieved without deleting at least one vertex, so output 1 on the fourth line.
  • For k=5, the goal can be achieved without deleting any vertices. Thus, output 0 on the fifth line.

Sample Input 2

5 5
1 1
1 2
3 1
3 1
3 5

Sample Output 2

1
0
-1
-1
-1

G is not necessarily connected. Also, G may have multi-edges or self-loops.