题目描述

$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$ とした時の問題に対する答えである.

题目大意

存在 $n$ 个小镇，$m$ 条传送通道，第 $i$ 条双向连结 $u_i, v_i$ 两个小镇，经过每个传送通道需要花费 $1$ 分钟。特别地，可能存在 $u_i = 0$，表示该条传送通道只规定了一端，另一端待定。存在 $n$ 个独立询问，对于 $i = 1, 2, \cdots, n$，钦定所有未确定的 $u_i$ 均为 $i$，求从小镇 $1$ 到小镇 $n$ 最小耗费的时间。若无法到达输出 $-1$。

3 2
0 2
1 2

-1 -1 2

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

3 3 3 3 2

提示

制約

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

Sample Explanation 1

結ぶ先が未定となっているテレポーターの結び先を町 $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$ つの町を結ぶテレポーターが複数存在する可能性がある事に注意してください。