Searching For Bread

View as PDF

Submit solution

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

Comments

There are no comments at the moment.