Problem Description

There is a binary tree with $n(n \le 10^6)$ nodes. You are given the indices of the two child nodes for each node (both not exceeding $n$). Build a binary tree (the root node has index $1$). If a node is a leaf, the input is 0 0.

After building the binary tree, find its depth. The depth of a binary tree means the maximum number of levels passed when going from the root node to a leaf node.

Input Format

The first line contains an integer $n$, which is the number of nodes.

Then follow $n$ lines. In the $i$-th line, two integers $l$ and $r$ are given, representing the indices of the left and right child nodes of node $i$, respectively. If $l=0$, it means there is no left child node; similarly, $r=0$ means there is no right child node.

Output Format

One integer, representing the maximum node depth.

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

4

Hint

Translated by ChatGPT 5