問題文

あおいちゃんの住む国には $N$ 個の町があり、町にはそれぞれ $1$ から $N$ までの番号が割り振られています。
また、町同士を繋ぐ一方通行の道が $M$ 本あります。 $i$ 本目 $(1 \leq i \leq M)$ の道は町 $u_i$ から町 $v_i$ へ移動することが可能です。

あおいちゃんはお姉ちゃんの頼みで、以下のようなおつかいをします。

• 町 $1$ の自宅から出発し、町 $N-1$ と町 $N$ の両方に少なくとも $1$ 回以上訪れ、再び町 $1$ の自宅に戻る。

おつかいの移動経路の中で最短のものの長さ (通る道ののべ本数) を求めてください。
ただし、おつかいが不可能な場合は -1 を出力してください。

制約

• $3 \leq N \leq 10^5$
• $0 \leq M \leq \min(10^5, N(N-1))$
• $1 \leq u_i, v_i \leq N$
• $u_i \ne v_i$
• $i \ne j \Longrightarrow (u_i, v_i) \ne (u_j, v_j)$
• 入力は全て整数

入力

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

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

出力

答えを出力してください。おつかいが不可能な場合は -1 を出力してください。

サンプル

サンプル1

入力サンプルをコピー

入力

4 6
1 2
2 4
2 3
3 1
3 4
4 3

出力

4

あおいちゃんの住む国は下図のようになっています。
おつかいの経路として例えば、 町 $1$ $\rightarrow$ 町 $2$ $\rightarrow$ 町 $4$ $\rightarrow$ 町 $3$ $\rightarrow$ 町 $1$ が挙げられます。
実はこれが最短経路なので、通った道ののべ本数である $4$ を出力します。

3 3
1 2
3 1
2 1

-1

7 12
1 2
1 4
1 5
2 5
3 1
3 2
4 1
4 6
5 1
5 6
6 7
7 3

5