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.
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 one integer \(T\), the taste of the tastiest bread Stephen can get.
\(2 \le N \le 1000\)
\(N-1 \le M \le 2000\)
5 4 1 2 1 3 2 4 4 5