Find the Diameter of a Tree
You are given a tree with
v vertices and your task is to find the diameter of the tree. The diameter is the length of the path between the two furthermost vertices.Input
The first line of the input contains a single integer
v (1 ≤ v ≤ 100 000).The following
v-1 lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.Output
The program should print the diameter of the given tree.
Examples
Input | Output |
3
1 2
1 3 | 2 |
5
1 2
1 3
3 4
3 5 | 3 |
Hint 1
You can perform DFS multiple times from different sources
Hint 2
You can perform DFS starting from node 1 and find the furthermost vertex (as this is a tree, meaning there are no cycles, we can do that without BFS).
Then start a DFS from the found furthermost vertex and find the farthest vertex from that one.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB