F - Blocked Roads Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点 M 辺の有向グラフが与えられます。頂点には 1 から N の番号、辺には 1 から M の番号がついています。辺 i\,(1 \leq i \leq M) は頂点 s_i から頂点 t_i に向かう長さ 1 の辺です。

各 i\,(1 \leq i \leq M) について、辺 i のみ通れないときの頂点 1 から頂点 N までの最短距離を求めてください。ただし、頂点 1 から頂点 N にたどり着けない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 400
  • 1 \leq M \leq N(N-1)
  • 1 \leq s_i,t_i \leq N
  • s_i \neq t_i
  • (s_i,t_i) \neq (s_j,t_j) (i \neq j)
  • 入力は全て整数である。

入力

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

N M
s_1 t_1
s_2 t_2
\vdots
s_M t_M

出力

M 行出力せよ。

i 行目には、辺 i のみ通れないときの頂点 1 から頂点 N までの最短距離を出力せよ。ただし、頂点 1 から頂点 N にたどり着けない場合は -1 を出力せよ。

入力例 1

3 3
1 2
1 3
2 3

出力例 1

1
2
1

入力例 2

4 4
1 2
2 3
2 4
3 4

出力例 2

-1
2
3
2

辺 1 のみ通れないとき、頂点 1 から頂点 N にたどり着けないので -1 を出力します。

入力例 3

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

出力例 3

1
1
3
1
1
1
1
1
1
1

入力例 4

4 1
1 2

出力例 4

-1

Score : 500 points

Problem Statement

You are given a directed graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i (1 \leq i \leq M) goes from Vertex s_i to Vertex t_i and has a length of 1.

For each i (1 \leq i \leq M), find the shortest distance from Vertex 1 to Vertex N when all edges except Edge i are passable, or print -1 if Vertex N is unreachable from Vertex 1.

Constraints

  • 2 \leq N \leq 400
  • 1 \leq M \leq N(N-1)
  • 1 \leq s_i,t_i \leq N
  • s_i \neq t_i
  • (s_i,t_i) \neq (s_j,t_j) (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
s_1 t_1
s_2 t_2
\vdots
s_M t_M

Output

Print M lines.

The i-th line should contain the shortest distance from Vertex 1 to Vertex N when all edges except Edge i are passable, or -1 if Vertex N is unreachable from Vertex 1.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

1
2
1

Sample Input 2

4 4
1 2
2 3
2 4
3 4

Sample Output 2

-1
2
3
2

Vertex N is unreachable from Vertex 1 when all edges except Edge 1 are passable, so the corresponding line contains -1.

Sample Input 3

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

Sample Output 3

1
1
3
1
1
1
1
1
1
1

Sample Input 4

4 1
1 2

Sample Output 4

-1