問題説明

ねこ村に「ニャンニャン路線」というミニ電車網ができました。 駅は通路で直接つながっており、つながった2つの駅は1回で移動できます。 すべての通路の長さは同じと考えてかまいません（重みなし）。 出発駅から目的駅まで行くには、通路に最低何回乗ればよいでしょうか？ 通路に1回乗ることを「移動1回」と数えます。

入力

出力

制約条件

• •1 ≤ N ≤ 1000
• •通路は双方向で重み（距離）はすべて同じ
• •同じ2駅の間に通路が重複して与えられる場合がある

例

7 7
0 1
0 2
1 3
3 4
2 5
5 4
2 6
0 4

3