配点 : $500$ 点

問題文

$N$ 個の町と $M$ 個のテレポーターがあり、 町は町 $1$, 町 $2$, $\ldots$, 町$N$ と番号づけられています。 それぞれのテレポーターは $2$ つの町を双方向に結んでおり、テレポーターを使用する事によってその $2$ つの町の間を $1$ 分で移動することができます。

$i$ 番目のテレポーターは町 $U_i$ と町 $V_i$ を双方向に結んでいますが、 いくつかのテレポーターについては結ぶ町の片方が決まっておらず、 $U_i=0$ のときそのテレポーターが結ぶ町の片方は町 $V_i$ であるが、 もう片方が未定であることを意味します。

$i=1,2,\ldots,N$ それぞれについて、次の問題を解いてください。

結ぶ町の片方が未定となっているテレポーターの結ぶ先をすべて町 $i$ とする。 この時に町 $1$ から町 $N$ まで移動するのに最小で何分かかるか求めよ。 町 $1$ から町 $N$ までテレポーターのみを使って移動するのが不可能な場合は $-1$ を出力せよ。

制約

• $2 \leq N \leq 3\times 10^5$
• $1\leq M\leq 3\times 10^5$
• $0\leq U_i
• $i \neq j$ ならば $(U_i,V_i)\neq (U_j,V_j)$
• 入力は全て整数

入力

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

$N$ $M$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

出力

$N$ 個の整数を空白区切りで出力せよ。 ここで、$k$ 番目の整数は $i=k$ とした時の問題に対する答えである.

3 2
0 2
1 2

-1 -1 2

結ぶ先が未定となっているテレポーターの結び先を町 $1$ としたとき、 $1$ 番目と $2$ 番目のテレポーターはともに町 $1$ と町 $2$ を結びます。 このとき、町 $1$ から町 $3$ への移動はできません。

結ぶ先が未定となっているテレポーターの結び先を町 $2$ としたとき、 $1$ 番目のテレポーターは町 $2$ 同士を、 $2$ 番目のテレポーターは町 $1$ と町 $2$ を結びます。 このときもやはり、町 $1$ から町 $3$ への移動はできません。

結ぶ先が未定となっているテレポーターの結び先を町 $3$ としたとき、 $1$ 番目のテレポーターは町 $3$ と町 $2$ を、 $2$ 番目のテレポーターは町 $1$ と町 $2$ を結びます。 この時、次のようにして町 $1$ から町 $3$ へ $2$ 分で移動できます。

• $2$ 番目のテレポーターを使用し、町 $1$ から町 $2$ まで移動する。
• $1$ 番目のテレポーターを使用し、町 $2$ から町 $3$ まで移動する。

よって、$-1,-1,2$ をこの順に出力します。

結ぶ先が未定となっているテレポーターの結び先によっては、 同じ町同士を結ぶテレポーターが存在する可能性や、 ある $2$ つの町を結ぶテレポーターが複数存在する可能性がある事に注意してください。

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

3 3 3 3 2