Diameter of Binary Tree

Problem statement

A maintenance network forms a binary tree of stations. Technicians want the greatest number of links on a simple route between any two stations, not necessarily a route that starts at the central station. Your task Compute the diameter of the binary tree, measured in edges on its longest path. Important details A path cannot revisit a node. Its endpoints may lie in different branches of a deep subtree, so the longest path need not pass through the root. An empty tree and a single-node tree both have diameter zero. Worked example With root 1 and two leaf children 2 and 3, the longest path is 2 -> 1 -> 3. It contains two edges, so the diameter is 2.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print the diameter in edges.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

3
1 1 2
2 -1 -1
3 -1 -1

Sample output

2