AT_abc257_f [ABC257F] Teleporter Setting

[problemUrl]: https://atcoder.jp/contests/abc257/tasks/abc257_f $ 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 $ を出力せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

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

### 制約 - $ 2\ \leq\ N\ \leq\ 3\times\ 10^5 $ - $ 1\leq\ M\leq\ 3\times\ 10^5 $ - $ 0\leq\ U_i\