Stephen loves bread. He loves it so much that he knows every bakery in the city. There are ~N~ bakeries, named ~1 \ldots N~ with ~M~ routes connecting them. The tastiness of the bread, ~T~, is determined based on its distance from Stephen's house. The farther away the bakery, the better the bread tastes. Stephen lives at bakery ~1~ and wants to know how tasty the tastiest bread is.

Note: Stephen will only take the most optimal (shortest) path to each bakery.

Input Specification

The first line of input will contain two integers, ~N~ and ~M~, the number of bakeries and number of roads, respectively.

The next ~M~ lines will contain two integers ~A~ and ~B~, indicating the bakery ~A~ and bakery ~B~ are connected.

Output Specification

Output one integer ~T~, the taste of the tastiest bread Stephen can get.

Constraints

~2 \le N \le 1000~

~N-1 \le M \le 2000~

Sample Input

5 4
1 2
1 3 
2 4
4 5

Sample Output

3