Consider an unrooted tree with vertices numbered from to connected by edges of length . We define the diameter of a tree as the longest path between any two vertices of the tree.
We can modify the tree to maximize its diameter by performing the following moves exactly once:
- Remove one edge from the tree so that it splits into two smaller trees.
- Pick one vertex from each of the two trees and join them by adding an edge.
For example, the diameter of the initial tree in the diagram below is , but we can increase this to by removing the edge between vertices and and adding an edge connecting vertices and :
Given a tree, print the maximum possible diameter after modifying the tree.
Input Format
The first line contains an integer denoting (the number of vertices).
Each of the subsequent lines contains two space-separated integers, and , defining an edge connecting vertex and vertex .
Constraints
Subtasks
- for of the maximum score.
Output Format
Print the maximum possible diameter after modifying the tree.
Sample Input 0
4
1 2
2 3
2 4
Sample Output 0
3
Explanation 0
The optimal solution for this tree is diagrammed in the Problem Statement above.