题目描述

《二叉树的最大宽度》

【二叉树的最大宽度】 给定一棵二叉树，求它的最大宽度。 本题中树的第i层的宽度定义为：第i层最左边的结点到最右边的结点之间的结点数量，包含最左右结点且包含中间的空结点。

输入格式

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

输出格式

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

样例

输入样例 1

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

输出样例 1

4

输入样例 2

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

输出样例 2

4

输入样例 3

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

输出样例 3

2

输入样例 4

1
-1 -1

输出样例 4

1