题目描述

有一个 n 个结点的二叉树。给出每个结点的两个子结点编号，建立一棵二叉树。

根结点编号为 1。如果某个子结点不存在，则输入 0。

请输出这棵二叉树的深度。二叉树的深度是指从根结点到叶子结点时，最多经过了几层。

输入格式

第一行一个整数 n，表示结点数。

之后 n 行，第 i 行包含两个整数 l、r，分别表示结点 i 的左子结点编号和右子结点编号。

若 l = 0，则表示没有左子结点；若 r = 0，则表示没有右子结点。

输出格式

输出一个整数，表示这棵二叉树的最大深度。

样例输入

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

样例输出

4

数据范围

对于全部数据，1 <= n <= 1000000。

提示

本题可以用深度优先搜索或广度优先搜索求树的最大深度。

如果使用递归，链状树可能导致递归层数过深。更稳妥的写法是用队列或数组模拟遍历。