391. The Longest Walk in a Tree

Challenge1000 ms256 MBSolved by 0%

The input is guaranteed to be a tree: connected, and with exactly n - 1 edges. Print its diameter, the number of edges on the longest path between any two vertices.

The obvious approach is to run a breadth-first search from every vertex and take the largest distance found. That is correct and it is O(n²), which is too slow here.

There is a much better method and it is only two searches.

1. Search from any vertex, say vertex 1, and let a be a vertex at maximum distance from it. 2. Search from a. The largest distance found is the diameter.

The claim behind step 1 is the interesting part: the farthest vertex from ANY starting point is always an endpoint of some longest path. Try it on the fifth test, where vertex 1 is in the middle and the answer is 4 rather than the 2 a single search from vertex 1 reports.

Constraints - `1 ≤ n ≤ 100000` - `m = n - 1` - The input is always a tree: connected and without cycles.

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 diameter of the tree.

Input5 4 1 2 2 3 3 4 4 5

Output4

Noteis a straight path, where the diameter is every edge

Input5 4 1 2 1 3 1 4 1 5

Output2

Noteis a star, where the longest walk is leaf to centre to leaf

Input7 6 1 2 1 3 2 4 2 5 3 6 3 7

Output4

Notehas vertex 1 in the middle, so one search from vertex 1 reports 2 and the answer is 4

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution