题目描述

$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 を出力してください。

输入格式

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

$N$ $M$ $s_1$ $t_1$ $s_2$ $t_2$ $\vdots$ $s_M$ $t_M$

输出格式

$M$ 行出力せよ。

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

题目大意

题目大意

给定一张 $n$ 个点，$m$ 条边的有向图，每条边的边权均为 $1$。请对于每一个 $i\in [1,m]$ 求出从点 $1$ 到 $n$ 的不经过第 $i$ 条边的最短路长度。

Translated by _Ponder_

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

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

提示

制約

• $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)$
• 入力は全て整数である。

Sample Explanation 2

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