001 - Fastest Path in HOJ

時間制限 1 秒 / メモリ制限 64 MB / 得点 10 / x 3 /


TLE
1sec
MLE
64MB
得点
10

問題

$HOJ$国では駅1,駅2,...,駅$N$の$N$個の駅があります。
$HOJ$国の電車の情報が$M$個与えられます。$i$番目($1 \leq i \leq M$)の情報は整数の$2$つ組($A_i$,$B_i$)で表され、次のような意味を持ちます。
・駅$A_i$と駅$B_i$の間を10分で移動できる
これらの情報に該当しない電車は存在せず、電車以外の方法で駅から異なる駅へ移動することはできません。
また、乗り換えにかかる時間及び待ち時間は無視します。
駅1から駅$N$まで移動するのにかかる時間を求めてください。
ただし、移動することができない場合は-1を出力してください。

入力

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

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
 :
$A_M$ $B_M$

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $2 \leq N \leq 10^{5}$
  • $1 \leq M \leq 10^{5}$
  • $1 \leq A_i, B_i \leq N$
  • $A_i \ne B_i(1 \leq i \leq N)$
  • 入力はすべて整数

入出力例

入力例1

5 4
1 2
2 3
3 4
4 5

出力例1

40

入力例2

4 2
1 2
3 4

出力例2

-1