20120106 - 二叉树的深度和宽度

通过次数

5

提交次数

17

Time Limit : 1 秒
Memory Limit : 128 MB

有一颗二叉树,如下图:

此二叉树共有7个结点①②③④⑤⑥⑦,并约定结点①为根结点,处在第一层。根结点①有2个孩子,左孩子为②,右孩子为③,并约定二叉树的一个结点最多有2个孩子。 二叉树可以用三元式表示,(结点    左孩子    右孩子) 对于上图的二叉树可以表示为:

上面二叉树的深度为4(即最大层次数),宽度为3(即,同一层上最多结点数)。

Input

第一行一个整数(1≤n≤30),即结点个数。

接下来 n行,每行三个数,即结点三元式。

Output

一行,含二个整数,即二叉树深度和宽度

Examples

Input

4
1 2 3
2 4 0
3 0 0
4 0 0 

Output

3 2