392. How Far Is the Furthest

Core1000 ms256 MBSolved by 0%

Print the distance from vertex 1 to the vertex furthest from it, counted in edges. Print -1 if any vertex cannot be reached from vertex 1 at all.

This number is called the eccentricity of vertex 1.

The search is the one from problem 364, run once. What this problem adds is that you must notice the unreachable case rather than quietly reporting the furthest thing you happened to find. A graph in two pieces has a largest distance inside vertex 1's own piece, and reporting it would be wrong.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.

Input

The first line contains two integers n and m, the number of vertices and edges. Each of the next m lines contains two integers u and v, an undirected edge between those vertices. Vertices are numbered 1 to n.

Output

Print one integer, the largest distance from vertex 1, or -1 if some vertex is unreachable.

Input5 4 1 2 2 3 3 4 4 5

Output4

Noteis a path with vertex 1 at one end

Input5 4 1 2 2 3 3 1 4 5

Output-1

Notehas a second component, so a solution that just takes its own maximum answers 1 instead

Input5 4 1 2 1 3 1 4 1 5

Output1

Noteis a star centred on vertex 1, so nothing is further than one step

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution