1665 - 2番目に短い道

問題

$N$頂点$M$辺の無向グラフが与えられる。
頂点$１$から頂点$Ｎ$に同じ頂点を通らずに行く経路で２番目に短い経路の長さを出力してください。
そのような経路がない場合は$-1$を出力してください。
ただし、このグラフには、二重辺や自己ループは存在しない。
初めて作ったから間違ってたらごめんね☆

入力

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

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

1行目に整数$N$,$M$が与えられる。 2からM+1行目に整数$A_i$,$B_i$が与えられる。 このとき、頂点$A_i$と頂点$B_i$がつながっていることを表す。

出力

$ANS$

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

制約

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

• $2 \leq N \leq 100$
• $1 \leq M \leq N$
• $1 \leq A_i,B_i \leq N$

入出力例

入力例1

4 4
1 2
2 3
2 4
3 4

出力例1

3

入力例2

2 1
1 2

出力例2

-1