题目描述

给定一棵二叉树， 求该二叉树的宽度。 二叉树宽度的定义： 是指具有节点数目最多的那一层的节点个数，即所有层中节点数的最大值。

输入格式

第一行是一个整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n， 根结点为 1， n <= 10 。接下来有 n 行， 依次对应二叉树的 n 个结点。 每行有两个整数， 分别表示该结点的左儿子和右儿子的结点编号。 如果第一个（第二个） 数为-1 则表示没有左（右）儿子。

输出格式

输出一个整型数， 表示树的宽度。

样例

输入样例 1

3
2  3
-1 -1
-1 -1

输出样例 1

2

输入样例 2

7
2  7
3 6
4 5
-1 -1
-1 -1
-1 -1
-1 -1

输出样例 2

2

输入样例 3

1
-1 -1

输出样例 3

1

提示

提示：使用队列逐层遍历，统计每层节点数，最大值就是树的宽度。