自転車の坂道

Emil は都市 1 から都市 n へ自転車で旅をしようとしています。しかし、これらの都市を結ぶ道路には上り坂や下り坂があり、移動の際に一筋縄ではいきません。特に、Emil が上り坂から下り坂、あるいは下り坂から上り坂に切り替わる時には、快適さを保つために自転車のギアを変えなければなりません。ここで知りたいのは、都市 1 から都市 n へ移動する間にギアを変える最小回数です。

Emil が都市 1 から都市 n まで移動する際に必要となるギアチェンジの最小回数を出力してください。

入力

最初の行には、都市の数と道路の数を表す 2 つの整数 n と m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) が空白区切りで与えられます。

続く m 行には、それぞれ 2 つの空白区切りの整数 と (, ) が含まれます。これは都市 と を結ぶ道路を示しており、 から へ向かう道路は上り坂、逆に から へ向かう道路は下り坂です。

出力

プログラムは、都市 1 から都市 n へ移動する間に Emil がギアを変更しなければならない最小回数を表す整数を 1 つ出力してください。

例