Maximum Depth of Binary Tree

Problem statement

A branching inspection route is represented by a binary tree. The planner needs to know how many stations an inspector could visit on the longest route that starts at the entrance and repeatedly follows a child branch until reaching a terminal station. Your task Compute the maximum depth of the tree: the largest number of nodes on any path from the root to a leaf. Important details A leaf has no children. Count nodes rather than edges, so a single-node tree has depth one. An empty tree has depth zero. A path may pass through nodes with only one child. Worked example An entrance 4 with child 2, whose own child is 1, has a longest root-to-leaf path containing three stations. The depth is 3.

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 maximum depth.

Constraints

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

Sample input

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

Sample output

3