VU atrankinis turas 2005 m. ACM ICPC varžyboms

Suppose we want to draw a binary tree in a grid obeying the following rules:

1. Nodes in the same level must be in the same row.
2. Each column can have only one node.
3. Nodes in the left subtree of a node must be to the left of the node and nodes in the right subtree must be to the right of the node.
4. There can be no columns between the leftmost column of the tree and the rightmost column of the tree that do not contain any nodes.

The levels are numbered from 1 starting form the root node. The width of each level is defined to be the distance from the left edge of the column of the leftmost node to the right edge of the column of the rightmost node in the level.

The following figure shows a binary tree drawn obeying the above rules. The width of the first level is 1, the width of the second level is 13, and the widths of the third, fourth, fifth, and sixth are 18, 18, 13, and 12, respectively.

Given a binary tree, write a program to compute the level with the maximal width and the width of that level.

Input

The first line of input file contains a single integer N (1 ≤ N ≤ 1,000), the number of nodes in the tree. The nodes are numbered from 1 to N, with 1 being the root node. Each of the following N lines consists of three integers, where the first is a node and the second and the third are the left and the right child of the first node, respectively. A missing child is denoted by -1.

Output

The first and only line of the output file must contain two integers: the level with the maximal width and its width. If there are several levels with the maximal width, output the smallest level number.

Sample Input

19
1 2 3
2 4 5
3 6 7
4 8 -1
5 9 10
6 11 12
7 13 -1
8 -1 -1
9 14 15
10 -1 -1
11 16 -1
12 -1 -1
13 17 -1
14 -1 -1
15 18 -1
16 -1 -1
17 -1 19
18 -1 -1
19 -1 -1

Sample Output

3 18