配点 : $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 を出力せよ。

3 3
1 2
1 3
2 3

1
2
1

4 4
1 2
2 3
2 4
3 4

-1
2
3
2

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

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

1
1
3
1
1
1
1
1
1
1

4 1
1 2

-1