Binary Tree Maximum Depth

You are given a binary tree with n nodes. Each node is represented by two integers which denote the indices of its left and right children respectively. If a child does not exist, the index is given as -1. The tree is provided in a 1-indexed manner. Your task is to compute the maximum depth of the tree.

The maximum depth of a binary tree is defined as:

[ \text{max_depth} = \begin{cases} 0, & \text{if the tree is empty} \ 1 + \max(\text{max_depth(left)}, \text{max_depth(right)}), & \text{otherwise} \end{cases} ]

where max_depth(left) and max_depth(right) are the depths of the left and right subtrees, respectively.

inputFormat

The input is given from standard input (stdin) and has the following format:

n
left_1 right_1
left_2 right_2
... 
left_n right_n

Here, the first line contains a single integer n indicating the number of nodes. The next n lines each contain two integers representing the indices of the left and right child of the corresponding node. A value of -1 indicates that there is no child in that position.

outputFormat

Output a single integer which is the maximum depth of the binary tree to standard output (stdout).

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

3