問題文

$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