View as PDF

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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